FAST
Changkyu Kim, Jatin Chhugani, Nadathur Satish et al. · Proceedings - ACM-SIGMOD International Conference on Management of Data · 2010
In-memory tree structured index search is a fundamental database operation. Modern processors provide tremendous computing power by integrating multiple cores, each with wide vector units. There has been much work to exploit modern processor architectures for database primitives like scan, sort, join and aggregation. However, unlike other primitives, tree search presents significant challenges due to irregular and unpredictable data accesses in tree traversal.
Cited by 306 works. doi:10.1145/1807167.1807206
Authors
- Changkyu Kim
- Jatin Chhugani
- Nadathur Satish
- Eric Sedlar
- Anthony D. Nguyen
- Tim Kaldewey
- Scott Brandt
- Pradeep Kumar Dubey
References
- Ubiquitous B-Tree
- Larrabee
- Prefix B -trees
- Integrating compression and execution in column-oriented database systems
- Making B+- trees cache conscious in main memory
- Super-Scalar RAM-CPU Cache Compression
- Cache Conscious Indexing for Decision-Support in Main Memory
- A Study of Index Structures for Main Memory Database Management Systems
- Compressing relations and indexes
- Efficient implementation of sorting on multi-core SIMD CPU architecture