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: h77798c4d51de6184
Venue: PODS
Year: 2015
Pagerank: 5.2503805e-05
Overall Rank: 8,959 | 39.77%
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,605	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	6.5047683e-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,163	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.00011750813
1,461	Substring Selectivity Estimation	1999	PODS	0.00010583833
6,952	Space-efficient Substring Occurrence Estimation	2011	PODS	5.635646e-05

Semantically Similar Papers

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