On Searching Compressed String Collections Cache-Obliviously

Summary: Cache-friendly compressed edge-linearizations of tries: new analyses of front coding and novel layouts that approach information-theoretic space while reducing cache misses. A distribution-aware dictionary encoding yields near-optimal space and competitive I/O-search, and a succinct cache-oblivious trie variant combines both. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: hf331d38f1b0de07f
Venue: PODS
Year: 2008
Pagerank: 5.2278394e-05
Overall Rank: 9,110 | 38.75%
DOI: 10.1145/1376916.1376943

Incoming Non-self Citations Over Time

Authors

1. Paolo Ferragina (University of Pisa)
2. Roberto Grossi (University of Pisa)
3. Ankur Gupta (Butler University)
4. Rahul Shah (Louisiana State University)
5. Jeffrey Scott Vitter (Purdue University)

BibTeX Citation

@inproceedings{ferragina_pods08,
        address = {New York, NY, USA},
        series = {{PODS} '08},
        title = {{On Searching Compressed String Collections Cache-Obliviously}},
        url = {https://dl.acm.org/doi/10.1145/1376916.1376943},
        doi = {10.1145/1376916.1376943},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ferragina, Paolo and Grossi, Roberto and Gupta, Ankur and Shah, Rahul and Vitter, Jeffrey Scott},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,155	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.9456729e-05
4,955	The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space	2012	PODS	6.3406617e-05

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
1,074	Cache-Oblivious String B-trees	2006	PODS	0.00012162592

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,889	An Efficient Index Structure for String Databases	2001	VLDB
2	5,397	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD
3	1,589	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS
4	3,816	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB
5	2,179	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS
6	9,786	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
7	12,445	MRCSI: Compressing and Searching String Collections with Multiple References	2015	VLDB
8	910	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
9	4,955	The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space	2012	PODS
10	1,074	Cache-Oblivious String B-trees	2006	PODS