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: 1457
Venue: PODS
Year: 2008
Pagerank: 5.3458888e-05
Overall Rank: 8,951 | 38.59%
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,150	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	9.081101e-05
4,911	The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space	2012	PODS	6.4483493e-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,112	Cache-Oblivious String B-trees	2006	PODS	0.00012125766

Semantically Similar Papers

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