DBScholar

Back to papers

FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs

Summary: FAST is architecture-sensitive binary-tree index layout for CPUs/GPUs, aligned to cache lines, page size, and SIMD to reduce traversal latency. 50M CPU/GPU queries/sec (5x/1.7x faster); bulk rebuilds <0.1s for 64M keys; compression mitigates memory bandwidth. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h4c198aad1e560d80
Venue
SIGMOD
Year
2010
Pagerank
0.00022264207
Overall Rank
282 | 98.11%
DOI
10.1145/1807167.1807206

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{kim_sigmod10,
        title = {{FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs}},
        author = {Kim, Changkyu and Chhugani, Jatin and Satish, Nadathur and Sedlar, Eric and Nguyen, Anthony D. and Kaldewey, Tim and Lee, Victor W. and Brandt, Scott A. and Dubey, Pradeep},
        series = {{SIGMOD} '10},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1807167.1807206},
        url = {https://dl.acm.org/doi/10.1145/1807167.1807206},
        year = {2010}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 54 citing papers.

Rank Citing Paper Year Venue Pagerank
40 The Case for Learned Index Structures 2018 SIGMOD 0.00046284649
365 Hyder - A Transactional Record Manager for Shared Flash 2011 CIDR 0.00019941855
430 ALEX: An Updatable Adaptive Learned Index 2020 SIGMOD 0.00018409112
627 Rethinking SIMD Vectorization for In-Memory Databases 2015 SIGMOD 0.00015460957
779 FITing-Tree: A Data-aware Index Structure 2019 SIGMOD 0.00014030069
848 Benchmarking Learned Indexes 2021 VLDB 0.00013506188
907 HOT: A Height Optimized Trie Index for Main-Memory Database Systems 2018 SIGMOD 0.00013158824
1,116 A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort 2014 SIGMOD 0.00011962096
1,283 A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing 2016 VLDB 0.00011209209
1,335 Fast Updates on Read-Optimized Databases Using Multi-Core CPUs 2012 VLDB 0.0001099401
1,550 Updatable Learned Index with Precise Positions 2021 VLDB 0.00010282449
1,605 The Data Calculator*: Data Structure Design and Cost Synthesis from First Principles and Learned Cost Models 2018 SIGMOD 0.00010093796
1,855 PALM: Parallel Architecture-Friendly Latch-Free Modifications to B+ Trees on Many-Core Processors 2011 VLDB 9.4973014e-05
2,185 Database Compression on Graphics Processors 2010 VLDB 8.8948351e-05
2,277 FINEdex: A Fine-grained Learned Index Scheme for Scalable and Concurrent Memory Systems 2022 VLDB 8.7075835e-05
2,284 Pump Up the Volume: Processing Large Data on GPUs with Fast Interconnects 2020 SIGMOD 8.6954168e-05
2,383 The Uncracked Pieces in Database Cracking 2014 VLDB 8.5435328e-05
2,673 Asynchronous Memory Access Chaining 2016 VLDB 8.1482775e-05
2,809 Exploiting Coroutines to Attack the "Killer Nanoseconds" 2018 VLDB 7.9825078e-05
2,889 High-Throughput Transaction Executions on Graphics Processors 2011 VLDB 7.9070124e-05
2,925 Interleaving with Coroutines: A Practical Approach for Robust Index Joins 2018 VLDB 7.8482706e-05
3,001 ClickHouse - Lightning Fast Analytics for Everyone 2024 VLDB 7.7667824e-05
3,200 Why it is time for a HyPE: A Hybrid Query Processing Engine for Efficient GPU Coprocessing in DBMS 2013 VLDB 7.5437496e-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,393 CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster 2012 SIGMOD 7.3471344e-05
3,491 In-Cache Query Co-Processing on Coupled CPU-GPU Architectures 2015 VLDB 7.2619913e-05
3,599 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017 SIGMOD 7.1773938e-05
3,689 RTIndex: Exploiting Hardware-Accelerated GPU Raytracing for Database Indexing 2023 VLDB 7.0943075e-05
3,697 Learned Index: A Comprehensive Experimental Evaluation 2023 VLDB 7.0882335e-05
3,803 CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm 2022 VLDB 7.0127652e-05
4,539 OmniDB: Towards Portable and Efficient Query Processing on Parallel CPU/GPU Architectures 2013 VLDB 6.5532239e-05
4,721 Hist-Tree: Those Who Ignore It Are Doomed to Learn 2021 CIDR 6.4541703e-05
5,032 Put an Elephant into a Fridge: Optimizing Cache Efficiency for In-memory Key-value Stores 2020 VLDB 6.3053972e-05
5,394 Towards a Hybrid Design for Fast Query Processing in DB2 with BLU Acceleration Using Graphical Processing Units: A Technology Demonstration 2016 SIGMOD 6.1497789e-05
5,467 GPU Rasterization for Real-Time Spatial Aggregation over Arbitrary Polygons 2018 VLDB 6.119722e-05
5,775 Blockchains vs. Distributed Databases: Dichotomy and Fusion 2021 SIGMOD 5.9981539e-05
6,274 A Critical Analysis of Recursive Model Indexes 2022 VLDB 5.8271888e-05
6,399 Catalyst: Optimizing Cache Management for Large In-memory Key-value Systems 2023 VLDB 5.798136e-05
6,906 MILC: Inverted List Compression in Memory 2017 VLDB 5.6498626e-05
7,018 SALI: A Scalable Adaptive Learned Index Framework based on Probability Models 2023 SIGMOD 5.619958e-05
7,169 Automatic Synthesis of Out-of-Core Algorithms 2013 SIGMOD 5.594516e-05
7,535 Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid Construction 2024 SIGMOD 5.5003117e-05
7,710 The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures 2022 VLDB 5.4713723e-05
8,174 Hyperion: Building the Largest In-memory Search Tree 2019 SIGMOD 5.3839613e-05
8,380 Interleaved Multi-Vectorizing 2020 VLDB 5.3429493e-05
8,619 Accelerating Pathology Image Data Cross-Comparison on CPU-GPU Hybrid Systems 2012 VLDB 5.3016441e-05
8,873 Why Are Learned Indexes So Effective but Sometimes Ineffective? 2025 VLDB 5.2582842e-05
9,201 An Application-Specific Instruction Set for Accelerating Set-Oriented Database Primitives 2014 SIGMOD 5.2083769e-05
9,683 S3: A Scalable In-memory Skip-List Index for Key-Value Store 2019 VLDB 5.1426496e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
61 Integrating Compression and Execution in Column-Oriented Database Systems 2006 SIGMOD 0.000392237
69 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00037950385
207 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00024970987
210 Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs 2009 VLDB 0.00024851502
219 SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units 2009 VLDB 0.00024363532
229 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00023911856
287 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00021970198
548 Improving Index Performance through Prefetching 2001 SIGMOD 0.00016569534
626 Adaptive Aggregation on Chip Multiprocessors 2007 VLDB 0.00015473276
722 Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture 2008 VLDB 0.00014488003
910 Dictionary-based Order-preserving String Compression for Main Memory Column Stores 2009 SIGMOD 0.00013123912
999 Data Compression Support in Databases 1994 VLDB 0.00012617745
1,107 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00011993663
1,586 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010146135
1,841 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 9.5268075e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 13,377 Fast Search In Main Memory Databases 1992 SIGMOD
2 6,123 Parallel Index-based Stream Join on a Multicore CPU 2020 SIGMOD
3 548 Improving Index Performance through Prefetching 2001 SIGMOD
4 1,841 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD
5 6,434 An Eight-Dimensional Systematic Evaluation of Optimized Search Algorithms on Modern Processors 2018 VLDB
6 5,411 GTS: GPU-based Tree Index for Fast Similarity Search 2024 SIGMOD
7 4,163 Distributing a Search Tree Among a Growing Number of Processors 1994 SIGMOD
8 11,237 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB
9 9,786 Memory-Efficient Search Trees for Database Management Systems 2021 SIGMOD
10 3,375 A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms 2016 SIGMOD