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.00024981343
Overall Rank
206 | 98.62%
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
68 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00037957995
70 The End of an Architectural Era (It’s Time for a Complete Rewrite) 2007 VLDB 0.00037851432
157 OLTP Through the Looking Glass, and What We Found There 2008 SIGMOD 0.00028316479
277 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00022320139
287 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00022001327
304 GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management 2006 SIGMOD 0.00021598803
422 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00018488849
458 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00017880664
547 Improving Index Performance through Prefetching 2001 SIGMOD 0.00016575635
616 Relational Joins on Graphics Processors 2008 SIGMOD 0.00015554627
675 Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing) 2010 VLDB 0.00014880686
702 Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct 2009 VLDB 0.00014668058
761 Conjunctive Selection Conditions in Main Memory 2002 PODS 0.00014138079
910 Dictionary-based Order-preserving String Compression for Main Memory Column Stores 2009 SIGMOD 0.00013122392
939 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.00012964695
1,041 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00012354465
1,105 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00011991167
1,438 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010647473
1,454 Fast Computation of Database Operations using Graphics Processors 2004 SIGMOD 0.00010596726
1,525 Updatable Learned Index with Precise Positions 2021 VLDB 0.00010355133
1,586 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010143882
1,716 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.8041694e-05
1,839 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 9.5284548e-05
1,857 PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors 2011 VLDB 9.4935317e-05
2,019 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.1749414e-05
2,270 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 8.7166469e-05
2,509 WHAM: A High-throughput Sequence Alignment Method 2011 SIGMOD 8.3675232e-05
3,003 ClickHouse - Lightning Fast Analytics for Everyone 2024 VLDB 7.7631056e-05
3,358 RUMA has it: Rewired User-space Memory Access is Possible! 2016 VLDB 7.377868e-05
3,374 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 7.3606793e-05
3,710 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 7.0775695e-05
4,026 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.8430008e-05
4,715 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 6.4537149e-05
4,873 Improving Database Performance on Simultaneous Multithreading Processors 2005 VLDB 6.370725e-05
5,068 Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage 2024 SIGMOD 6.2872138e-05
6,125 Parallel Index-based Stream Join on a Multicore CPU 2020 SIGMOD 5.8761704e-05
6,321 Robust Performance of Main Memory Data Structures by Configuration 2020 SIGMOD 5.8126925e-05
6,908 MILC: Inverted List Compression in Memory 2017 VLDB 5.6471881e-05
7,190 GPUQP: Query Co-Processing Using Graphics Processors 2007 SIGMOD 5.5881603e-05
7,498 B^link-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases 2023 VLDB 5.5078165e-05
7,714 The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures 2022 VLDB 5.4699237e-05
7,920 Cache-Oblivious Query Processing 2007 CIDR 5.4250739e-05
8,179 Hyperion: Building the Largest In-memory Search Tree 2019 SIGMOD 5.3816264e-05
8,229 The HV-tree: a Memory Hierarchy Aware Version Index 2010 VLDB 5.3726119e-05
9,559 B-Trees Are Back: Engineering Fast and Pageable Node Layouts 2025 SIGMOD 5.1577035e-05
9,680 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 5.1421471e-05
9,777 Lachesis: Robust Database Storage Management Based on Device-specific Performance Characteristics 2003 VLDB 5.1300274e-05
10,440 Concurrent Path-Copying Update to Tree Structures 2026 SIGMOD 4.9769913e-05
10,737 SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory 2026 VLDB 4.9769913e-05
11,131 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 4.9769913e-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.0023943337
76 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00036891569
223 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00024120979
229 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00023915204
611 "One Size Fits All" Database Architectures Do Not Work For DSS 1995 SIGMOD 0.00015572934
820 Dali: A High Performance Main Memory Storage Manager 1994 VLDB 0.00013658052
1,384 Query Processing in Main Memory Database Management Systems 1986 SIGMOD 0.00010842059
1,801 Hash joins and hash teams in Microsoft SQL Server 1998 VLDB 9.604827e-05
2,146 A Recovery Algorithm for A High-Performance Memory-Resident Database System 1987 SIGMOD 8.9573718e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 12,785 Worst-Case Efficient Range Search Indexing 2009 PODS
2 6,070 When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories 2023 SIGMOD
3 9,792 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,839 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD
6 1,075 Cache-Oblivious String B-trees 2006 PODS
7 1,716 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB
8 2,019 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD
9 1,105 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB
10 68 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD