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: h4ae2f6ac7bf432e3
Venue: VLDB
Year: 1999
Pagerank: 0.00024970987
Overall Rank: 207 | 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
11,237	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.9793485e-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.0023947656
76	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00036898845
223	AlphaSort: A RISC Machine Sort	1994	SIGMOD	0.0002412513
229	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00023911856
611	"One Size Fits All" Database Architectures Do Not Work For DSS	1995	SIGMOD	0.00015574329
820	Dali: A High Performance Main Memory Storage Manager	1994	VLDB	0.00013661724
1,384	Query Processing in Main Memory Database Management Systems	1986	SIGMOD	0.00010845169
1,802	Hash joins and hash teams in Microsoft SQL Server	1998	VLDB	9.6081518e-05
2,145	A Recovery Algorithm for A High-Performance Memory-Resident Database System	1987	SIGMOD	8.9603529e-05

Semantically Similar Papers

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