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.4682399e-05
Overall Rank: 8,657 | 39.84%
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,442	Brighthouse: An Analytic Data Warehouse for Ad-hoc Queries	2008	VLDB	8.8067249e-05
4,886	The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space	2012	PODS	5.8508915e-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,113	Cache-Oblivious String B-trees	2006	PODS	0.00013885755

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,330	An Efficient Index Structure for String Databases	2001	VLDB	6.2745131e-05
5,847	Order-Preserving Key Compression for In-Memory Search Trees	2020	SIGMOD	5.3040014e-05
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
4,215	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3464157e-05
2,018	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7852268e-05
9,499	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3300131e-05
11,964	MRCSI: Compressing and Searching String Collections with Multiple References	2015	VLDB	4.1905499e-05
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013751593
4,886	The Wavelet Trie: Maintaining an Indexed Sequence of Strings in Compressed Space	2012	PODS	5.8508915e-05
1,113	Cache-Oblivious String B-trees	2006	PODS	0.00013885755