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: 1458
Venue: PODS
Year: 2008
Pagerank: 4.4722862e-05
Overall Rank: 8,660 | 39.76%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,444	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.8076551e-05
4,897	The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space	2012	PODS	5.8469152e-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,117	Cache-Oblivious String B-trees	2006	PODS	0.00013882205

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,333	An Efficient Index Structure for String Databases	2001	VLDB	6.2805237e-05
5,835	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	5.30905e-05
1,502	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643406
4,216	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3521675e-05
2,013	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7928688e-05
9,498	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3341665e-05
11,956	MRCSI: Compressing and Searching String Collections with Multiple References	2015	VLDB	4.1945683e-05
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013761456
4,897	The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space	2012	PODS	5.8469152e-05
1,117	Cache-Oblivious String B-trees	2006	PODS	0.00013882205