The Case for Learned Index Structures
Jeff Dean and co at GOOG just released a paper showing how machine-learned indexes can replace B-Trees, Hash Indexes, and Bloom Filters. Execute 3x faster than B-Trees, 10-100x less space. Executes on GPU, which are getting faster unlike CPU. Amazing.
The paper is here, and there’s also a presentation (via Hacker News).
Update (2018-01-08): See also: Adrian Colyer.
Update (2018-01-09): See also: Adrian Colyer.
Update (2018-01-14): Peter Bailis et al.:
While learned indexes are an exciting idea for many reasons (e.g., they could enable self-tuning databases), there is a long literature of other optimized data structures to consider, so naturally researchers have been trying to see whether these can do better.
