FINEdex: A Fine-grained Learned Index Scheme for Scalable and Co(5)

为了准确地找到被查询的键，学习的索引在最后一阶段存储了每个模型的绝对max_error，计算方法如下:
学习的指标实现了一个两阶段RMI指数，顶部是一个小的神经网络(NN)，底部是大量的线性回归模型。在学习的索引中，顶部的简单(0个隐藏层)到半复杂NN模型(2个隐藏层)比其他配置的NN模型(即更多的隐藏层)更有效。在底部执行复杂的模型是不划算的，因为简单的线性回归模型足够精确，可以学习小的子数据集。
2.2 The Scalability Requirements 所学习的索引是在静态分布的数据上进行训练的，并假设数据是由单个线程统一访问的，不考虑数据分布随时间变化的情况。为了支持高可伸缩性，学习到的索引必须满足以下要求。
插入而不丢失数据。插入的基本要求是保证可以找到所有的数据，包括距离中心函数最远的数据(即训练过的模型)。对于学习到的索引，不应该将新的数据直接插入到训练好的数据数组中，以避免由于数据移动而导致一些数据找不到的错误。例如，如图2b所示，蓝线代表实际数据分布，红线代表其中一个线性回归模型，黑点为该模型覆盖的数据。由于max_error(即模型的最大误差)由式1计算，因此点a的误差x满足条件:

其中abs()返回绝对值。点a由模型找到，因为真实位置满足条件:
其中pred_a表示a的预测结果，当有新插入的数据时，并不是所有的覆盖点都能被找到。例如，当插入的数据小于a时，我们需要将点a移动到a '以保持所有数据的排序，从而导致一个错误:
由于新的错误abs(x) > max_error。
保持所有数据的排序，以便有效的范围查询。作为一个有序的索引结构，所有数据在插入时都需要保持排序，以获得高效的范围查询性能。否则，需要对查询的数据进行多次搜索，这会降低范围查询的性能。
适当的并发性。在扩展到大量核心和线程的系统中，提供并发操作变得非常重要。没有或很少有线程冲突通常有助于提高并发性能，特别是对于学习的索引在运行时插入和重新训练新数据。我们还需要避免数据不一致，即没有数据丢失或冗余。但是，对学习到的索引进行并发的再训练并不是一件简单的事情，因为再训练需要花费很长的时间来阻塞其他操作对数据的查询和再训练。