Cache Conscious Indexing for Decision-Support in Main Memory

Summary: Introduces cache-sensitive search trees (CSS-trees): cache-line-sized, pointerless directory arrays over sorted data, using offset arithmetic for navigation. Experiments show >2× faster lookups than binary search with low overhead, outperforming B+-, T-, and binary search trees. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8809
Venue: VLDB
Year: 1999
Pagerank: 0.00025342994
Overall Rank: 204 | 98.61%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jun Rao (Columbia University)
2. Kenneth A. Ross (Columbia University)

BibTeX Citation

@article{rao_vldb99,
        title = {{Cache Conscious Indexing for Decision-Support in Main Memory}},
        author = {Rao, Jun and Ross, Kenneth A.},
        journal = {PVLDB},
        series = {{VLDB} '99},
        pages = {78--89},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 51 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,829	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0024089429
74	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00037330605
215	AlphaSort: A RISC Machine Sort	1994	SIGMOD	0.00024507963
219	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00024293529
608	"One Size Fits All" Database Architectures Do Not Work For DSS	1995	SIGMOD	0.00015795625
821	Dali: A High Performance Main Memory Storage Manager	1994	VLDB	0.00013808096
1,355	Query Processing in Main Memory Database Management Systems	1986	SIGMOD	0.0001105702
1,809	Hash joins and hash teams in Microsoft SQL Server	1998	VLDB	9.7034998e-05
2,116	A Recovery Algorithm for A High-Performance Memory-Resident Database System	1987	SIGMOD	9.1439163e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,489	Worst-Case Efficient Range Search Indexing	2009	PODS
2	5,954	When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories	2023	SIGMOD
3	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
4	219	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB
5	1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
6	1,112	Cache-Oblivious String B-trees	2006	PODS
7	1,710	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB
8	1,978	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD
9	1,110	Buffering Accesses to Memory-Resident Index Structures	2003	VLDB
10	67	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD