Benchmarking Learned Indexes

Peephole optimization

W. M. McKeeman · 1965

Earlier work this paper cites.

An almost optimal algorithm for unbounded searching

J. L. Bentley and A. C.-C. Yao · 1976

Earlier work this paper cites.

B-tree indexes, interpolation search, and skew

G. Graefe · 2006

Earlier work this paper cites.

STX B+ Tree, https://panthema.net/2007/stx-btree/

2007

Earlier work this paper cites.

Smooth interpolating histograms with error guarantees

T. Neumann and S. Michel · 2008

Earlier work this paper cites.

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

C. Kim, J. Chhugani, N. Satish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V. W. Lee, S. A. Brandt, and P. Dubey · 2010

Earlier work this paper cites.

Efficient parallel lists intersection and index compression algorithms using graphics processing units

N. Ao, F. Zhang, D. Wu, D. S. Stones, G. Wang, X. Liu, J. Liu, and S. Lin · 2011

Earlier work this paper cites.

The adaptive radix tree: ARTful indexing for main-memory databases

V. Leis, A. Kemper, and T. Neumann · 2013

Earlier work this paper cites.

Maximum error-bounded Piecewise Linear Representation for online stream approximation

Q. Xie, C. Pang, X. Zhou, X. Zhang, and K. Deng · 2014

Earlier work this paper cites.

A seven-dimensional analysis of hashing methods and its implications on query processing

S. Richter, V. Alvarez, and J. Dittrich · 2015

Cited alongside, same era.

The Case for B-Tree Index Structures (blog post), http://databasearchitects.blogspot.com/2017/12/the-case-for-b-tree-index-structures.html, 2017

Peter Boncz and Thomas Neumann · 2017

Cited alongside, same era.

HOT: A height optimized trie index for main-memory database systems

R. Binna, E. Zangerle, M. Pichl, G. Specht, and V. Leis · 2018

Cited alongside, same era.

The Case for Learned Index Structures

T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis · 2018

Cited alongside, same era.

Don’t Throw Out Your Algorithms Book Just Yet: Classical Data Structures That Can Outperform Learned Indexes (blog post), https://dawn.cs.stanford.edu/2018/01/11/index-baselines/, 2018

Peter Bailis, Kai Sheng Tai, Pratiksha Thaker, and Matei Zaharia · 2018

Cited alongside, same era.

SOSD: A Benchmark for Learned Indexes

A. Kipf, R. Marcus, A. van Renen, M. Stoian, A. Kemper, T. Kraska, and T. Neumann · 2019

Later among the works it cites.

Learning Multi-dimensional Indexing

V. Nathan, J. Ding, M. Alizadeh, and T. Kraska · 2019

Later among the works it cites.

Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?

P. Van Sandt, Y. Chronis, and J. M. Patel · 2019

Later among the works it cites.

Wormhole: A Fast Ordered Index for In-memory Data Management

X. Wu, F. Ni, and S. Jiang · 2019

Later among the works it cites.

Learned data structures

P. Ferragina and G. Vinciguerra · 2020

Closest in time.

The PGM-index: A fully-dynamic compressed learned index with provable worst-case bounds

P. Ferragina and G. Vinciguerra · 2020

Closest in time.