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.00013885755
Overall Rank: 1,113 | 92.27%
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.00024954332
608	Monkey: Optimal Navigable Key-Value Store	2017	SIGMOD	0.00019233548
941	Wander Join: Online Aggregation via Random Walks	2016	SIGMOD	0.00015147831
1,249	Don't Thrash: How to Cache Your Hash on Flash	2012	VLDB	0.00013040265
1,309	Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging	2018	SIGMOD	0.00012655712
1,368	SlimDB: A Space-Efficient Key-Value Storage Engine For Semi-Sorted Data	2017	VLDB	0.0001235708
1,932	X-Engine: An Optimized Storage Engine for Large-scale E-commerce Transaction Processing	2019	SIGMOD	0.00010050776
2,112	The Log-Structured Merge-Bush & the Wacky Continuum	2019	SIGMOD	9.5244583e-05
2,606	Design Continuums and the Path Toward Self-Designing Key-Value Stores that Know and Learn	2019	CIDR	8.4621503e-05
3,365	An Adaptive Packed-Memory Array	2006	PODS	7.1675736e-05
3,970	Spooky: Granulating LSM-Tree Compactions Correctly	2022	VLDB	6.5756727e-05
5,118	Design Tradeoffs of Data Access Methods	2016	SIGMOD	5.6781464e-05
7,373	Cache-Oblivious Query Processing	2007	CIDR	4.744464e-05
7,467	GeckoFTL: Scalable Flash Translation Techniques For Very Large Flash Devices	2016	SIGMOD	4.7174456e-05
8,657	On Searching Compressed String Collections Cache-Obliviously	2008	PODS	4.4682399e-05
9,858	Performance Guarantees for B-trees with Different-Sized Atomic Keys	2010	PODS	4.2652623e-05
10,571	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.1905499e-05
10,917	Layered List Labeling	2024	PODS	4.1905499e-05
10,920	History-Independent Dynamic Partitioning: Achieving Operation-Order Privacy in Ordered Data Structures	2024	PODS	4.1905499e-05
11,448	Learning Algorithms for Automatic Data Structure Design	2021	SIGMOD	4.1905499e-05
11,566	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	4.1905499e-05
11,772	Write-Optimized Skip Lists	2017	PODS	4.1905499e-05
11,830	Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries	2016	PODS	4.1905499e-05
11,926	Purity: Building Fast, Highly-Available Enterprise Flash Storage from Commodity Components	2015	SIGMOD	4.1905499e-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,586	Practical Suffix Tree Construction	2004	VLDB	8.4894627e-05
14,362	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.00013751593
4,317	Compact B-Trees	1979	SIGMOD	6.2824978e-05
8,770	Compact O-Complete Trees	1988	VLDB	4.4520434e-05
9,499	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3300131e-05
240	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00031526134
104	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00049475932
14,306	Towards an Optimal Data-Structure: CB-trees	1984	VLDB	-
8,657	On Searching Compressed String Collections Cache-Obliviously	2008	PODS	4.4682399e-05