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: 1394
Venue: PODS
Year: 2006
Pagerank: 0.00012125766
Overall Rank: 1,112 | 92.38%
DOI: 10.1145/1142351.1142385

Incoming Non-self Citations Over Time

Authors

1. Michael A. Bender (State University of New York at Stony Brook)
2. Martin Farach-Colton (Rutgers University)
3. Bradley C. Kuszmaul (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{bender_pods06,
        address = {New York, NY, USA},
        series = {{PODS} '06},
        title = {{Cache-Oblivious String B-trees}},
        url = {https://dl.acm.org/doi/10.1145/1142351.1142385},
        doi = {10.1145/1142351.1142385},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Bender, Michael A. and Farach-Colton, Martin and Kuszmaul, Bradley C.},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 24 of 24 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
275	bLSM: A General Purpose Log Structured Merge Tree	2012	SIGMOD	0.00022630189
446	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00018332392
593	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00016027871
789	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.0001401724
831	Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging	2018	SIGMOD	0.00013748512
857	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.00013568886
1,347	X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing	2019	SIGMOD	0.00011073571
1,502	The Log-Structured Merge-Bush & the Wacky Continuum	2019	SIGMOD	0.00010557694
1,942	Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn	2019	CIDR	9.4451535e-05
2,950	An Adaptive Packed-Memory Array	2006	PODS	7.9260861e-05
3,054	Spooky: Granulating LSM-Tree Compactions Correctly	2022	VLDB	7.8090808e-05
4,826	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.4904836e-05
7,249	GeckoFTL: Scalable Flash Translation Techniques For Very Large Flash Devices	2016	SIGMOD	5.6634301e-05
7,792	Cache-Oblivious Query Processing	2007	CIDR	5.5431413e-05
8,951	On Searching Compressed String Collections Cache-Obliviously	2008	PODS	5.3458888e-05
10,009	Performance Guarantees for B-trees with Different-Sized Atomic Keys	2010	PODS	5.1785299e-05
10,829	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	5.093636e-05
11,134	Layered List Labeling	2024	PODS	5.093636e-05
11,137	History-Independent Dynamic Partitioning: Achieving Operation-Order Privacy in Ordered Data Structures	2024	PODS	5.093636e-05
11,643	Learning Algorithms for Automatic Data Structure Design	2021	SIGMOD	5.093636e-05
11,759	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	5.093636e-05
11,970	Write-Optimized Skip Lists	2017	PODS	5.093636e-05
12,025	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	5.093636e-05
12,117	Purity: Building Fast, Highly-Available Enterprise Flash Storage from Commodity Components	2015	SIGMOD	5.093636e-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
1	14,479	An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees	1984	SIGMOD
2	14,549	Multi-Table Search For B-Tree Files	1979	SIGMOD
3	925	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
4	6,246	Compact B-Trees	1979	SIGMOD
5	8,943	Compact O-Complete Trees	1988	VLDB
6	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
7	204	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB
8	67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD
9	14,493	Towards an Optimal Data-Structure: CB-trees	1984	VLDB
10	8,951	On Searching Compressed String Collections Cache-Obliviously	2008	PODS