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
8619
Venue
VLDB
Year
1999
Pagerank
0.00031526134
Overall Rank
240 | 98.34%
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
88 The End of an Architectural Era (It's Time for a Complete Rewrite) 2007 VLDB 0.0005262025
104 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00049475932
215 OLTP Through the Looking Glass, and What We Found There 2008 SIGMOD 0.00033609709
238 GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management 2006 SIGMOD 0.00031596093
343 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00026756534
382 FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs 2010 SIGMOD 0.00024888997
622 Improving Index Performance through Prefetching 2001 SIGMOD 0.00018976783
754 Database Architecture Evolution: Mammals Flourished long before Dinosaurs became Extinct 2009 VLDB 0.00017093267
771 Relational Joins on Graphics Processors 2008 SIGMOD 0.00016813054
789 Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing) 2010 VLDB 0.00016602215
790 Conjunctive Selection Conditions in Main Memory 2002 PODS 0.0001659522
819 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00016237497
844 The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds 2020 VLDB 0.00015964123
1,046 Buffering Database Operations for Enhanced Instruction Cache Performance 2004 SIGMOD 0.00014446882
1,100 Generic Database Cost Models for Hierarchical Memory Systems 2002 VLDB 0.00014062265
1,134 Dictionary-based Order-preserving String Compression for Main Memory Column Stores 2009 SIGMOD 0.00013751593
1,195 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00013404419
1,659 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010970279
1,670 Speedup Graph Processing by Graph Ordering 2016 SIGMOD 0.00010944596
1,685 Fast Computation of Database Operations using Graphics Processors 2004 SIGMOD 0.0001090924
1,807 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 0.0001047644
1,947 WHAM: A High-throughput Sequence Alignment Method 2011 SIGMOD 9.9963826e-05
1,987 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.8561164e-05
1,999 PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors 2011 VLDB 9.8287642e-05
2,233 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.2299873e-05
2,550 Updatable Learned Index with Precise Positions 2021 VLDB 8.5569576e-05
3,136 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 7.4926368e-05
3,627 Cache-conscious Frequent Pattern Mining on a Modern Processor 2005 VLDB 6.900129e-05
3,760 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD 6.7790524e-05
3,919 RUMA has it: Rewired User-space Memory Access is Possible! 2016 VLDB 6.6260396e-05
4,498 ClickHouse - Lightning Fast Analytics for Everyone 2024 VLDB 6.1351257e-05
4,830 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 5.8884997e-05
5,154 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 5.6548237e-05
5,226 Improving Database Performance on Simultaneous Multithreading Processors 2005 VLDB 5.6164816e-05
5,857 Spruce: A Fast yet Space-saving Structure for Dynamic Graph Storage 2024 SIGMOD 5.2970837e-05
6,469 Parallel Index-based Stream Join on a Multicore CPU 2020 SIGMOD 5.0448159e-05
6,566 Robust Performance of Main Memory Data Structures by Configuration 2020 SIGMOD 5.0030559e-05
7,160 MILC: Inverted List Compression in Memory 2017 VLDB 4.8088037e-05
7,373 Cache-Oblivious Query Processing 2007 CIDR 4.744464e-05
7,375 GPUQP: Query Co-Processing Using Graphics Processors 2007 SIGMOD 4.7439007e-05
8,069 The HV-tree: a Memory Hierarchy Aware Version Index 2010 VLDB 4.5893806e-05
8,080 Hyperion: Building the Largest In-memory Search Tree 2019 SIGMOD 4.5872476e-05
8,408 The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures 2022 VLDB 4.5159669e-05
9,383 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 4.343888e-05
9,448 Lachesis: Robust Database Storage Management Based on Device-specific Performance Characteristics 2003 VLDB 4.3368058e-05
10,257 SIDLE: Tree-structure Aware Indexes for CXL-based Heterogeneous Memory 2026 VLDB 4.1905499e-05
10,380 B-Trees Are Back: Engineering Fast and Pageable Node Layouts 2025 SIGMOD 4.1905499e-05
10,407 VEGA: An Active-tuning Learned Index with Group-Wise Learning Granularity 2025 SIGMOD 4.1905499e-05
10,571 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 4.1905499e-05
11,231 Blink-hash: An Adaptive Hybrid Index for In-Memory Time-Series Databases 2023 VLDB 4.1905499e-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.0040465394
81 Cache Conscious Algorithms for Relational Query Processing 1994 VLDB 0.00055253195
85 AlphaSort: A RISC Machine Sort 1994 SIGMOD 0.00053652634
235 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00031980259
456 "One Size Fits All" Database Architectures Do Not Work For DSS 1995 SIGMOD 0.00022703892
511 Dali: A High Performance Main Memory Storage Manager 1994 VLDB 0.0002139773
1,337 Query Processing in Main Memory Database Management Systems 1986 SIGMOD 0.00012515176
1,688 A Recovery Algorithm for A High-Performance Memory-Resident Database System 1987 SIGMOD 0.00010898703
1,902 Hash joins and hash teams in Microsoft SQL Server 1998 VLDB 0.0001015225
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
12,302 Worst-Case Efficient Range Search Indexing 2009 PODS 4.1905499e-05
6,226 When Tree Meets Hash: Reducing Random Reads for Index Structures on Persistent Memories 2023 SIGMOD 5.1413982e-05
9,499 Memory-Efficient Search Trees for Database Management Systems 2021 SIGMOD 4.3300131e-05
235 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00031980259
1,807 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 0.0001047644
1,113 Cache-Oblivious String B-trees 2006 PODS 0.00013885755
2,233 Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems 2001 VLDB 9.2299873e-05
1,987 Optimizing Multidimensional Index Trees for Main Memory Access 2001 SIGMOD 9.8561164e-05
1,195 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00013404419
104 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00049475932