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: h028cbc66c0aa4a19
Venue: PODS
Year: 2006
Pagerank: 0.00012122621
Overall Rank: 1,077 | 92.79%
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 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
261	bLSM: A General Purpose Log Structured Merge Tree	2012	SIGMOD	0.00022862412
402	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00019070605
594	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015814493
761	Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging	2018	SIGMOD	0.00014191047
791	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.00013927839
814	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.00013697533
1,324	X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing	2019	SIGMOD	0.00011019001
1,429	The Log-Structured Merge-Bush & the Wacky Continuum	2019	SIGMOD	0.00010685393
1,900	Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn	2019	CIDR	9.3926585e-05
2,882	Spooky: Granulating LSM-Tree Compactions Correctly	2022	VLDB	7.894356e-05
2,989	An Adaptive Packed-Memory Array	2006	PODS	7.7656181e-05
4,897	Design Tradeoffs of Data Access Methods	2016	SIGMOD	6.3489205e-05
7,411	GeckoFTL: Scalable Flash Translation Techniques For Very Large Flash Devices	2016	SIGMOD	5.5164757e-05
7,931	Cache-Oblivious Query Processing	2007	CIDR	5.4076475e-05
9,138	On Searching Compressed String Collections Cache-Obliviously	2008	PODS	5.2082006e-05
10,237	Performance Guarantees for B-trees with Different-Sized Atomic Keys	2010	PODS	5.0432098e-05
10,829	Dynamic read & write optimization with TurtleKV	2026	VLDB	4.9605343e-05
11,301	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.9605343e-05
11,540	Layered List Labeling	2024	PODS	4.9605343e-05
11,543	History-Independent Dynamic Partitioning: Achieving Operation-Order Privacy in Ordered Data Structures	2024	PODS	4.9605343e-05
12,000	Learning Algorithms for Automatic Data Structure Design	2021	SIGMOD	4.9605343e-05
12,112	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	4.9605343e-05
12,317	Write-Optimized Skip Lists	2017	PODS	4.9605343e-05
12,369	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	4.9605343e-05
12,459	Purity: Building Fast, Highly-Available Enterprise Flash Storage from Commodity Components	2015	SIGMOD	4.9605343e-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,835	An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees	1984	SIGMOD
2	14,892	Multi-Table Search For B-Tree Files	1979	SIGMOD
3	912	Dictionary-based Order-preserving String Compression for Main Memory Column Stores	2009	SIGMOD
4	6,390	Compact B-Trees	1979	SIGMOD
5	9,135	Compact O-Complete Trees	1988	VLDB
6	9,824	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
7	209	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB
8	68	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD
9	14,848	Towards an Optimal Data-Structure: CB-trees	1984	VLDB
10	9,138	On Searching Compressed String Collections Cache-Obliviously	2008	PODS