DBScholar

Back to papers

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

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 50 of 51 citing papers.

Rank Citing Paper Year Venue Pagerank
69 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00037950385
70 The End of an Architectural Era (It’s Time for a Complete Rewrite) 2007 VLDB 0.00037859131
157 OLTP Through the Looking Glass, and What We Found There 2008 SIGMOD 0.00028317906
282 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00022264207
287 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00021970198
304 GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management 2006 SIGMOD 0.00021604795
430 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00018409112
463 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00017804544
548 Improving Index Performance through Prefetching 2001 SIGMOD 0.00016569534
616 Relational Joins on Graphics Processors 2008 SIGMOD 0.00015561564
673 Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing) 2010 VLDB 0.0001488755
702 Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct 2009 VLDB 0.00014673738
761 Conjunctive Selection Conditions in Main Memory 2002 PODS 0.00014143602
910 Dictionary-based Order-preserving String Compression for Main Memory Column Stores 2009 SIGMOD 0.00013123912
939 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.00012970078
1,041 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00012356709
1,107 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00011993663
1,440 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010641888
1,454 Fast Computation of Database Operations using Graphics Processors 2004 SIGMOD 0.00010601431
1,550 Updatable Learned Index with Precise Positions 2021 VLDB 0.00010282449
1,586 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010146135
1,717 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.8016891e-05
1,841 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 9.5268075e-05
1,855 PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors 2011 VLDB 9.4973014e-05
2,016 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.1771614e-05
2,277 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 8.7075835e-05
2,508 WHAM: A High-throughput Sequence Alignment Method 2011 SIGMOD 8.371338e-05
3,001 ClickHouse - Lightning Fast Analytics for Everyone 2024 VLDB 7.7667824e-05
3,358 RUMA has it: Rewired User-space Memory Access is Possible! 2016 VLDB 7.3812131e-05
3,375 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 7.3608441e-05
3,803 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 7.0127652e-05
4,027 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.8456902e-05
4,721 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 6.4541703e-05
4,871 Improving Database Performance on Simultaneous Multithreading Processors 2005 VLDB 6.3737342e-05
5,065 Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage 2024 SIGMOD 6.2901915e-05
6,123 Parallel Index-based Stream Join on a Multicore CPU 2020 SIGMOD 5.8789534e-05
6,317 Robust Performance of Main Memory Data Structures by Configuration 2020 SIGMOD 5.8154421e-05
6,906 MILC: Inverted List Compression in Memory 2017 VLDB 5.6498626e-05
7,188 GPUQP: Query Co-Processing Using Graphics Processors 2007 SIGMOD 5.5908064e-05
7,710 The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures 2022 VLDB 5.4713723e-05
7,816 B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases 2023 VLDB 5.4481832e-05
7,918 Cache-Oblivious Query Processing 2007 CIDR 5.4275933e-05
8,174 Hyperion: Building the Largest In-memory Search Tree 2019 SIGMOD 5.3839613e-05
8,222 The HV-tree: a Memory Hierarchy Aware Version Index 2010 VLDB 5.3751545e-05
9,683 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 5.1426496e-05
9,772 Lachesis: Robust Database Storage Management Based on Device-specific Performance Characteristics 2003 VLDB 5.1324546e-05
9,998 B-Trees Are Back: Engineering Fast and Pageable Node Layouts 2025 SIGMOD 5.0979044e-05
10,428 Concurrent Path-Copying Update to Tree Structures 2026 SIGMOD 4.9793485e-05
10,727 SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory 2026 VLDB 4.9793485e-05
11,122 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 4.9793485e-05
Previous Page 1 / 2 Next

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
Previous Page 1 / 1 Next

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