Cache-Oblivious String B-trees

Summary: Cache-oblivious string B-tree (COSB-tree): index with asymptotically optimal searches and near-optimal updates, size proportional to front-compressed keys, and memory-efficient key decompression. Supports range queries with no extra disk seeks and exploits cache-oblivious layouts to utilize all memory-hierarchy levels. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1395
Venue: PODS
Year: 2006
Pagerank: 0.00013882205
Overall Rank: 1,117 | 92.24%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
379	bLSM: A General Purpose Log Structured Merge Tree	2012	SIGMOD	0.0002493527
609	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.0001923446
943	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015145883
1,248	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.00013046661
1,311	Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging	2018	SIGMOD	0.00012657439
1,366	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.00012357685
2,004	X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing	2019	SIGMOD	9.811707e-05
2,109	The Log-Structured Merge-Bush & the Wacky Continuum	2019	SIGMOD	9.5318694e-05
2,606	Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn	2019	CIDR	8.4645832e-05
3,366	An Adaptive Packed-Memory Array	2006	PODS	7.1726818e-05
3,965	Spooky: Granulating LSM-Tree Compactions Correctly	2022	VLDB	6.5820028e-05
5,119	Design Tradeoffs of Data Access Methods	2016	SIGMOD	5.6807904e-05
7,378	Cache-Oblivious Query Processing	2007	CIDR	4.7480163e-05
7,472	GeckoFTL: Scalable Flash Translation Techniques For Very Large Flash Devices	2016	SIGMOD	4.7199619e-05
8,660	On Searching Compressed String Collections Cache-Obliviously	2008	PODS	4.4722862e-05
9,859	Performance Guarantees for B-trees with Different-Sized Atomic Keys	2010	PODS	4.269353e-05
10,562	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.1945683e-05
10,913	Layered List Labeling	2024	PODS	4.1945683e-05
10,916	History-Independent Dynamic Partitioning: Achieving Operation-Order Privacy in Ordered Data Structures	2024	PODS	4.1945683e-05
11,445	Learning Algorithms for Automatic Data Structure Design	2021	SIGMOD	4.1945683e-05
11,562	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	4.1945683e-05
11,764	Write-Optimized Skip Lists	2017	PODS	4.1945683e-05
11,822	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	4.1945683e-05
11,918	Purity: Building Fast, Highly-Available Enterprise Flash Storage from Commodity Components	2015	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,583	Practical Suffix Tree Construction	2004	VLDB	8.497732e-05
14,348	Multi-Table Search For B-Tree Files	1979	SIGMOD	-
1,134	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD	0.00013761456
4,324	Compact B-Trees	1979	SIGMOD	6.2885419e-05
8,773	Compact O-Complete Trees	1988	VLDB	4.456315e-05
9,498	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3341665e-05
238	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00031642425
103	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049150032
14,292	Towards an Optimal Data-Structure: CB-trees	1984	VLDB	-
8,660	On Searching Compressed String Collections Cache-Obliviously	2008	PODS	4.4722862e-05