CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm. (arXiv:2103.00858v3 [cs.DB] UPDATED)

Web: http://arxiv.org/abs/2103.00858

Learned indexes, which use machine learning models to replace traditional
index structures, have shown promising results in recent studies. Existing
learned indexes use heuristic rules to construct index structures, which are
often suboptimal and sensitive to data distribution. In this paper, we argue
that upper-level RMI nodes should focus on data partitioning instead of model
fitting, and show that it leads to much better results in real-world datasets.
We introduce entropy as a metric to quantify and characterize the models …

algorithm arxiv construction