The Case for Learned Index Structures Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, Neoklis Polyzotis

    "Our initial results show, that by using neural nets we are able to outperform cache-optimized B-Trees by up to 70% in speed while saving an order-of-magnitude in memory over several real-world data sets. More importantly though, we believe that the idea of replacing core components of a data management system through learned models has far reaching implications for future systems designs and that this work just provides a glimpse of what might be possible."

https://arxiv.org/abs/1712.01208

Note the other related submission today, which presents a learned index that claims “uniform improvement of the performance of RMI [this HN submission] in terms of query time and space occupancy”: https://news.ycombinator.com/item?id=25899286

Unless I'm missing something, PGM indexes blow RMI out of the water.

Direct link to the PGM page: https://pgm.di.unipi.it/

Yeah, apparently the results do not hold up under fair evaluation. They used a not well tuned RMI implementation. See: https://vldb.org/pvldb/vol14/p1-marcus.pdf

That said, PGMs are still interesting given their theoretical guarantees.