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
4318
Venue
SIGMOD
Year
2010
Pagerank
0.00022476841
Overall Rank
278 | 98.10%
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 4 of 54 citing papers.

Rank Citing Paper Year Venue Pagerank
9,518 Revisiting B-tree Compression: An Experimental Study 2024 SIGMOD 5.256602e-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
10,829 FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update 2025 VLDB 5.093636e-05
Previous Page 2 / 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
60 Integrating Compression and Execution in Column-Oriented Database Systems 2006 SIGMOD 0.0003955489
67 Making B+-Trees Cache Conscious in Main Memory 2000 SIGMOD 0.00038461275
204 Cache Conscious Indexing for Decision-Support in Main Memory 1999 VLDB 0.00025342994
209 Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs 2009 VLDB 0.00024932174
216 SIMD-Scan: Ultra Fast in-Memory Table Scan using on-Chip Vector Processing Units 2009 VLDB 0.00024498128
219 A Study of Index Structures for Main Memory Database Management Systems 1986 VLDB 0.00024293529
293 Implementing Database Operations Using SIMD Instructions 2002 SIGMOD 0.00022259273
545 Improving Index Performance through Prefetching 2001 SIGMOD 0.00016766463
632 Adaptive Aggregation on Chip Multiprocessors 2007 VLDB 0.00015575286
712 Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture 2008 VLDB 0.0001468812
925 Dictionary-based Order-preserving String Compression for Main Memory Column Stores 2009 SIGMOD 0.00013182044
1,017 Data Compression Support in Databases 1994 VLDB 0.00012641552
1,110 Buffering Accesses to Memory-Resident Index Structures 2003 VLDB 0.00012140661
1,567 Fractal Prefetching B+-Trees: Optimizing Both Cache and Disk Performance 2002 SIGMOD 0.00010343873
1,813 Main-Memory Index Structures with Fixed-Size Partial Keys 2001 SIGMOD 9.6941032e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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