FAST: fast architecture sensitive tree search on modern CPUs and GPUs

By Changkyu Kim, Jatin Chhugani, Nadathur Rajagopalan Satish, Eric Sedlar, Anthony D. Nguyen, Tim Kaldewey, Victor W. Lee, Scott A. Brandt, Pradeep K. Dubey. SIGMOD Conference, 2010

358 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/295521cfe1a56458d53a58613de5fb92c97c5c23

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Ed H. Chi
2. Alfons Kemper
3. Viktor Leis
4. Tim Kraska
5. Alex Beutel
6. Pradeep K. Dubey
7. Nadathur Rajagopalan Satish
8. Beng Chin Ooi

In Computer Networks and Communications

1. Viktor Leis
2. Alfons Kemper
3. Kian-Lee Tan
4. Johannes Gehrke
5. Beng Chin Ooi
6. Thomas Neumann
7. Gang Chen
8. Meihui Zhang

In Signal Processing

1. Johannes Gehrke
2. Kian-Lee Tan
3. Ed H. Chi
4. Beng Chin Ooi
5. Nadathur Rajagopalan Satish
6. Thomas Neumann
7. Alfons Kemper
8. Pradeep K. Dubey

Citations in the corpus

• The adaptive radix tree: ARTful indexing for main-memory databases (2013, methodology): “The k-ary search tree [6] and the Fast Architecture Sensitive Tree (FAST) [7] use data level parallelism to perform multiple comparisons simultaneously with Singe Instruction Multiple Data (SIMD) instructions.”
• Debunking the 100X GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU (2010, background): “Other studies which perform careful optimizations to CPU and GPU such as [27, 39, 40, 43, 49] report much lower speedup similar to ours.”
• Flat combining and the synchronization-parallelism tradeoff (2010, methodology): “FAST leverages architecture-specific knowledge to optimize B+tree’s layout in the memory to minimize cache and TLB misses [16].”
• The Case for Learned Index Structures (2017, methodology): “This may seem restrictive, but many modern hardware optimized B-Trees, e.g., FAST [44], make exactly the same assumptions, and these indexes are quite common for in-memory database systems for their superior performance [44, 48] over scanning or binary search.”
• ALEX: An Updatable Adaptive Learned Index (2019, methodology): “In addition to optimizing for cache performance, FAST [14] further optimizes searches within index nodes by exploiting SIMD parallelism.”
• In-Memory Big Data Management and Processing: A Survey (2015, methodology): “In addition, for memory-resident data structures, various cache-conscious indexes have been proposed such as Cache Sensitive Search Trees [81], Cache Sensitive B þ -Trees [82], Fast Architecture Sensitive Trees [85], and Adaptive Radix Trees [87].”