The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space

Summary: Compressed indexed sequences supporting random access, exact/prefix search, range counting and analytics in static and dynamic settings, stored in nearly-optimal (entropy) space. Wavelet Trie: combines Patricia trie with wavelet tree to enable dynamic alphabets and fast prefix queries in compressed space. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1577
Venue: PODS
Year: 2012
Pagerank: 6.4483493e-05
Overall Rank: 4,911 | 66.31%
DOI: 10.1145/2213556.2213586

Incoming Non-self Citations Over Time

Authors

1. Roberto Grossi (University of Pisa)
2. Giuseppe Ottaviano (Microsoft; University of Pisa)

BibTeX Citation

@inproceedings{grossi_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213586},
        doi = {10.1145/2213556.2213586},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Grossi, Roberto and Ottaviano, Giuseppe},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
8,951	On Searching Compressed String Collections Cache-Obliviously	2008	PODS	5.3458888e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,154	MRCSI: Compressing and Searching String Collections with Multiple References	2015	VLDB
2	8,078	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
3	925	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
4	2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD
5	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
6	8,810	Dynamic Data Structures for Document Collections and Graphs	2015	PODS
7	6,818	Space-efficient Substring Occurrence Estimation	2011	PODS
8	3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB
9	4,776	An Efficient Index Structure for String Databases	2001	VLDB
10	8,951	On Searching Compressed String Collections Cache-Obliviously	2008	PODS