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

Summary: For every MSO query on strings, builds a linear-time index supporting relabeling and single-symbol insertions/deletions in logarithmic time. Enumeration retains constant delay, avoiding the linear-time reconstruction required by prior dynamic indexes. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: h96780322750204ab
Venue: PODS
Year: 2018
Pagerank: 6.7244719e-05
Overall Rank: 4,205 | 71.82%
DOI: 10.1145/3196959.3196961

Incoming Non-self Citations Over Time

Authors

1. Matthias Niewerth (University of Bayreuth)
2. Luc Segoufin (INRIA; École Normale Supérieure)

BibTeX Citation

@inproceedings{niewerth_pods18,
        address = {New York, NY, USA},
        series = {{PODS} '18},
        title = {{Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates}},
        url = {https://dl.acm.org/doi/10.1145/3196959.3196961},
        doi = {10.1145/3196959.3196961},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Niewerth, Matthias and Segoufin, Luc},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,526	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.3274934e-05
4,173	Enumeration for FO Queries over Nowhere Dense Graphs	2018	PODS	6.7507874e-05
5,267	Complexity Bounds for Relational Algebra over Document Spanners	2019	PODS	6.1910223e-05
5,719	Enumeration on Trees with Tractable Combined Complexity and Efficient Updates	2019	PODS	6.0026773e-05
10,048	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS	5.0786422e-05
10,458	Optimal Enumeration of Regular Pattern Matches	2026	PODS	4.9605343e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
639	Answering Conjunctive Queries under Updates	2017	PODS	0.00015289346
5,187	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS	6.2228242e-05
13,954	Enumerating Answers to First-Order Queries over Databases of Low Degree	2014	PODS	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,051	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
2	2,766	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS
3	6,678	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
4	1,654	Indexing Moving Points (Extended Abstract)	2000	PODS
5	12,829	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
6	10,048	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS
7	5,187	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS
8	9,129	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
9	5,719	Enumeration on Trees with Tractable Combined Complexity and Efficient Updates	2019	PODS
10	9,104	Enumeration for MSO-Queries on Compressed Trees	2024	PODS