Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates

Matthias Niewerth 1 Luc Segoufin 2
2 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
Abstract : We consider the enumeration of MSO queries over strings under updates. For each MSO query we build an index structure enjoying the following properties: The index structure can be constructed in linear time, it can be updated in logarithmic time and it allows for constant delay time enumeration. This improves from the previous known index structures allowing for constant delay enumeration that would need to be reconstructed from scratch, hence in linear time, in the presence of updates. We allow relabeling updates, insertion of individual labels and removal of individual labels.
Document type :
Conference papers
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01895796
Contributor : Luc Segoufin <>
Submitted on : Tuesday, October 16, 2018 - 9:55:31 AM
Last modification on : Thursday, February 7, 2019 - 3:49:40 PM
Long-term archiving on : Thursday, January 17, 2019 - 12:49:19 PM

File

enum-update-words.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Matthias Niewerth, Luc Segoufin. Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates. Principles of Databse Systems, PODS'18, Jun 2018, Houston, United States. ⟨10.1145/3196959.3196961⟩. ⟨hal-01895796⟩

Share

Metrics

Record views

61

Files downloads

66