Database Paper Browser

Back to papers

Cache Conscious Indexing for Decision-Support in Main Memory

Summary: Proposes CSS-trees for main-memory decision-support: a cache-line sized directory atop a sorted array, no internal pointers, traversed by array offsets. Shows CSS-trees outperform B+-trees, T-trees, and BSTs in space and time, cutting binary-search costs by >2× due to fewer cache misses. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
8618
Venue
VLDB
Year
1999
Pagerank
0.00031642425
Overall Rank
238 | 98.35%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 50 citing papers.

Rank Citing Paper Year Venue Pagerank
86 The End of an Architectural Era (It's Time for a Complete Rewrite) 2007 VLDB 0.00052563276
103 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00049150032
215 OLTP Through the Looking Glass, and What We Found There 2008 SIGMOD 0.0003354907
239 GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management 2006 SIGMOD 0.00031617428
343 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00026768139
381 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00024873637
531 Improving Index Performance through Prefetching 2001 SIGMOD 0.00020790058
757 Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct 2009 VLDB 0.00017078358
775 Relational Joins on Graphics Processors 2008 SIGMOD 0.00016823862
794 Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing) 2010 VLDB 0.00016605103
795 Conjunctive Selection Conditions in Main Memory 2002 PODS 0.00016600368
826 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00016224841
857 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00015882892
1,050 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.00014453896
1,101 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00014070632
1,134 Dictionary-based Order-preserving String Compression for Main Memory Column Stores 2009 SIGMOD 0.00013761456
1,195 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00013406526
1,659 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010980701
1,676 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010946423
1,686 Fast Computation of Database Operations using Graphics Processors 2004 SIGMOD 0.00010917794
1,809 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 0.00010483957
1,944 WHAM: A High-throughput Sequence Alignment Method 2011 SIGMOD 0.00010004608
1,983 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.8638201e-05
2,006 PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors 2011 VLDB 9.8101551e-05
2,244 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.2097912e-05
2,552 Updatable Learned Index with Precise Positions 2021 VLDB 8.5530411e-05
3,131 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 7.4985793e-05
3,623 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.9062146e-05
3,777 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 6.7750901e-05
3,933 RUMA has it: Rewired User-space Memory Access is Possible! 2016 VLDB 6.617914e-05
4,495 ClickHouse - Lightning Fast Analytics for Everyone 2024 VLDB 6.1410277e-05
4,646 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 6.0250374e-05
5,157 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 5.6589595e-05
5,219 Improving Database Performance on Simultaneous Multithreading Processors 2005 VLDB 5.6217069e-05
5,847 Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage 2024 SIGMOD 5.302174e-05
6,476 Parallel Index-based Stream Join on a Multicore CPU 2020 SIGMOD 5.0496617e-05
6,574 Robust Performance of Main Memory Data Structures by Configuration 2020 SIGMOD 5.0055505e-05
7,377 GPUQP: Query Co-Processing Using Graphics Processors 2007 SIGMOD 4.7484565e-05
7,378 Cache-Oblivious Query Processing 2007 CIDR 4.7480163e-05
7,416 MILC: Inverted List Compression in Memory 2017 VLDB 4.7355258e-05
8,065 The HV-tree: a Memory Hierarchy Aware Version Index 2010 VLDB 4.5937864e-05
8,077 Hyperion: Building the Largest In-memory Search Tree 2019 SIGMOD 4.59165e-05
8,414 The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures 2022 VLDB 4.5203005e-05
9,373 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 4.3479874e-05
9,442 Lachesis: Robust Database Storage Management Based on Device-specific Performance Characteristics 2003 VLDB 4.3410889e-05
10,257 SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory 2026 VLDB 4.1945683e-05
10,368 B-Trees Are Back: Engineering Fast and Pageable Node Layouts 2025 SIGMOD 4.1945683e-05
10,396 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 4.1945683e-05
10,562 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.1945683e-05
11,229 Blink-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases 2023 VLDB 4.1945683e-05
Previous Page 1 / 1 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.0040449103
81 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00055548574
84 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00053866006
233 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00032021526
457 "One Size Fits All" Database Architectures Do Not Work For DSS 1995 SIGMOD 0.00022713791
510 Dali: A High Performance Main Memory Storage Manager 1994 VLDB 0.00021390381
1,309 Query Processing in Main Memory Database Management Systems 1986 SIGMOD 0.00012660929
1,691 A Recovery Algorithm for A High-Performance Memory-Resident Database System 1987 SIGMOD 0.00010903706
1,900 Hash joins and hash teams in Microsoft SQL Server 1998 VLDB 0.000101645
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,294 Worst-Case Efficient Range Search Indexing 2009 PODS 4.1945683e-05
6,229 When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories 2023 SIGMOD 5.1463389e-05
9,498 Memory-Efficient Search Trees for Database Management Systems 2021 SIGMOD 4.3341665e-05
233 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00032021526
1,809 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 0.00010483957
1,117 Cache-Oblivious String B-trees 2006 PODS 0.00013882205
2,244 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.2097912e-05
1,983 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.8638201e-05
1,195 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00013406526
103 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00049150032