![](https://csdnimg.cn/release/download_crawler_static/10226040/bg6.jpg)
2.
B-Trees, or decision trees in general, are really good in overfitting the data with a few operations as they
recursively divide the space using simple if-statement. In contrast, other models can be significantly
more efficient to approximate the general shape of a CDF, but have problems to be accurate at the
individual data instance level. To see this, consider again Figure 2. The figure demonstrates, that from
a top-level view, the CDF function appears very smooth and regular. However, if one zooms in to the
individual records, more and more irregularities show; a well known statistical effect. Many data sets
have exactly this behavior: from the top the data distribution appears very smooth, whereas as more is
zoomed in the harder it is to approximate the CDF because of the “randomness” on the individual level.
Thus models like neural nets, polynomial regression, etc., might be more CPU and space efficient to
narrow down the position for an item from the entire data set to a region of thousands, a single neural
net usually requires significantly more space and CPU time for the “last mile” to reduce the error
further drown from thousands to hundreds.
3.
The typical ML optimization goal is to minimize the average error. However, for indexing, where we
not only need the best guess where the item might be but also to actually find it, the min- and max-error
as discussed earlier are more important.
4.
B-Trees are extremely cache-efficient as they keep the top nodes always in cache and access other pages
if needed. However, other models are not as cache and operation efficient. For example, standard neural
nets require all weights to compute a prediction, which has a high cost in the number of multiplications
and weights, which have to brought in from memory.
3 The RM-Index
In order to overcome the challenges and explore the potential of models as index replacements or enrichments,
we developed the
learning index framework
(LIF), recursive-model indexes (RMI), and standard-error-
based search strategies. We mainly focus on simple, fully-connected neural nets simply because of their
simplicity, but many other types of models are possible.
3.1 The Learning Index Framework (LIF)
The LIF can be regarded as an index synthesis system; given an index specification, LIF generates different
index configurations, optimizes them, and tests them automatically. While LIF can learn simple models
on-the-fly (e.g., linear regression models), it relies on Tensorflow for more complex models (e.g., NN).
However, it never uses Tensorflow at inference. Rather, given a trained Tensorflow model, LIF automatically
extracts all weights from the model and generates efficient index structures in C++ based on the model
specification. While Tensorflow with XLA already supports code compilation, its focus is mainly on
large scale computations, where the execution of a model is on the scale of micro- or milli-seconds. In
contrast, our code-generation focuses on small models and thus, has to remove all unnecessary overhead
and instrumentation that Tensorflow has to manage the larger models. Here we leverage ideas from [
21
],
which already showed how to avoid unnecessary overhead from the Spark-runtime. As a result, we are able
to execute simple models on the order of 30 nano-seconds.
3.2 The Recursive Model Index
As outlined in Section 2.3 one of the key challenges of building alternative learned models to replace B-Trees
is the last-mile accuracy. For example, reducing the min-/max-error in the order of hundreds from 100M
records using a single model is very hard. At the same time, reducing the error to 10k from 100M, e.g., a
6