5 ms·
A Recursive Model learned index structure
- emayljames 6y agoThe 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 https://arxiv.org/abs/1712.01208
- jitl 6y agoNote 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 https://news.ycombinator.com/item?id=25899286
- jiggawatts 6y agoUnless I'm missing something, PGM indexes blow RMI out of the water. Direct link to the PGM page: https://pgm.di.unipi.it/ https://pgm.di.unipi.it/
- Traudl 6y agoYeah, 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 https://vldb.org/pvldb/vol14/p1-marcus.pdf That said, PGMs are still interesting given their theoretical guarantees.
- itsthecourier 6y agoFor sorted data in postgres I prefer BRIN indexes