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
8809
Venue
VLDB
Year
1999
Pagerank
0.00025342994
Overall Rank
204 | 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
67 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00038461275
68 The End of an Architectural Era (It’s Time for a Complete Rewrite) 2007 VLDB 0.00038446206
157 OLTP Through the Looking Glass, and What We Found There 2008 SIGMOD 0.0002863588
278 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00022476841
293 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00022259273
305 GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management 2006 SIGMOD 0.00021872796
447 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00018322593
477 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00017851226
545 Improving Index Performance through Prefetching 2001 SIGMOD 0.00016766463
631 Relational Joins on Graphics Processors 2008 SIGMOD 0.00015591241
660 Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing) 2010 VLDB 0.00015198804
721 Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct 2009 VLDB 0.00014631814
771 Conjunctive Selection Conditions in Main Memory 2002 PODS 0.00014161995
925 Dictionary-based Order-preserving String Compression for Main Memory Column Stores 2009 SIGMOD 0.00013182044
932 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.00013119305
1,028 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00012557617
1,110 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00012140661
1,452 Fast Computation of Database Operations using Graphics Processors 2004 SIGMOD 0.00010745803
1,511 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010538011
1,551 Updatable Learned Index with Precise Positions 2021 VLDB 0.00010381398
1,567 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010343873
1,710 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.9537123e-05
1,813 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 9.6941032e-05
1,822 PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors 2011 VLDB 9.6765747e-05
1,978 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.3627341e-05
2,233 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 8.8968964e-05
2,459 WHAM: A High-throughput Sequence Alignment Method 2011 SIGMOD 8.550768e-05
3,344 RUMA has it: Rewired User-space Memory Access is Possible! 2016 VLDB 7.4980897e-05
3,378 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 7.4587887e-05
3,653 ClickHouse - Lightning Fast Analytics for Everyone 2024 VLDB 7.2241143e-05
3,729 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 7.1683974e-05
3,969 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.9837297e-05
4,660 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 6.5797541e-05
4,772 Improving Database Performance on Simultaneous Multithreading Processors 2005 VLDB 6.5154736e-05
4,946 Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage 2024 SIGMOD 6.4319457e-05
6,012 Parallel Index-based Stream Join on a Multicore CPU 2020 SIGMOD 6.0102675e-05
6,187 Robust Performance of Main Memory Data Structures by Configuration 2020 SIGMOD 5.9485755e-05
6,791 MILC: Inverted List Compression in Memory 2017 VLDB 5.7723936e-05
7,113 GPUQP: Query Co-Processing Using Graphics Processors 2007 SIGMOD 5.6985502e-05
7,768 The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures 2022 VLDB 5.5475685e-05
7,792 Cache-Oblivious Query Processing 2007 CIDR 5.5431413e-05
8,015 Hyperion: Building the Largest In-memory Search Tree 2019 SIGMOD 5.5071737e-05
8,207 The HV-tree: a Memory Hierarchy Aware Version Index 2010 VLDB 5.4666057e-05
8,255 B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases 2023 VLDB 5.4574671e-05
9,498 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 5.2606222e-05
9,609 Lachesis: Robust Database Storage Management Based on Device-specific Performance Characteristics 2003 VLDB 5.2468818e-05
9,810 B-Trees Are Back: Engineering Fast and Pageable Node Layouts 2025 SIGMOD 5.214913e-05
10,212 Concurrent Path-Copying Update to Tree Structures 2026 SIGMOD 5.093636e-05
10,545 SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory 2026 VLDB 5.093636e-05
10,682 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 5.093636e-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.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
Previous Page 1 / 1 Next

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