Dynamic Data Structures for Document Collections and Graphs

Summary: Presents a framework to dynamize static compressed data structures, circumventing the Fredman–Saks rank lower bound that stymied prior compressed dynamic text indexes and nearly closing the static/dynamic indexing gap. Framework also yields compressed dynamic representations for graphs and binary relations supporting updates and pattern queries with near-static bounds. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1662
Venue: PODS
Year: 2015
Pagerank: 5.3654354e-05
Overall Rank: 8,810 | 39.56%
DOI: 10.1145/2745754.2745778

Incoming Non-self Citations Over Time

Authors

1. J. Ian Munro (University of Waterloo)
2. Yakov Nekrich (University of Waterloo)
3. Jeffrey Scott Vitter (University of Kansas)

BibTeX Citation

@inproceedings{munro_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{Dynamic Data Structures for Document Collections and Graphs}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745778},
        doi = {10.1145/2745754.2745778},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Munro, J. Ian and Nekrich, Yakov and Vitter, Jeffrey Scott},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,753	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	6.5231863e-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
1,140	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.0001200574
1,427	Substring Selectivity Estimation	1999	PODS	0.00010812749
6,818	Space-efficient Substring Occurrence Estimation	2011	PODS	5.7643154e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	925	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
2	9,472	Indexing for Keyword Search with Structured Constraints	2023	PODS
3	6,818	Space-efficient Substring Occurrence Estimation	2011	PODS
4	2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
5	896	On Indexing Mobile Objects	1999	PODS
6	7,141	Effective Indexing for Dynamic Structural Graph Clustering	2022	VLDB
7	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
8	10,450	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD
9	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
10	1,587	An Efficient Indexing Technique for Full-Text Database Systems	1992	VLDB