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

为了提供实用和准确的预测，将排序后的键和真实位置分别作为输入和输出。键和位置之间的关系是一条单调递增的曲线，类似于累积曲线分布函数(即CDF，有助于学习数据分布)，如图1b所示。图1b中使用的数据集与第5节中使用的数据集相同。在此基础上，通过学习数据分布的模式，可以提高预测精度。当通过已知回归模型准确表示键和位置之间的CDF时，由于每个位置都是由回归模型计算的，因此查找复杂度为O(1)。例如，一组连续的整数键(例如，从1到100M的键)存储在一个连续的位置(例如，从1到100M的位置)中。CDF表示为y=x，其中x和y是键和位置。因此，预测粒度为1，可以准确预测位置，无误差。然而，在实际应用中(例如，管理智能电表的数据，Facebook的pb级存储系统)，cdf无法提前获得，一些cdf变得极其复杂，甚至无法通过已知的回归模型来表示。
在这些情况下，我们不需要将预测粒度减小到1，因为B -树中叶子节点的长度从未设置为1，这简化了预测操作:回归模型只需要近似表示CDF，并将预测粒度减小到与B -树中的叶子节点相同的大小。

图1：Range index and CDF models. The CDFs are obtained by normalizing the keys and positions to 1.
使用单个ML模型来降低预测粒度(例如从100M到10)是困难的，这导致了复杂的ML模型。同时，这类模型的训练费用难以接受，设计和训练难度较大。所学习的指标提出了一种递归模型指标(RMI)来提高预测精度，该指标通过多个小ML模型，将预测粒度从100M逐渐降低到10K，再从10K逐渐降低到100。RMI的主要思想是建立一个模型层次结构，并通过训练好的模型预测键的位置。如图2a所示，RMI由3个阶段组成，分别包含1、2和3 ML模型。这些模型按照层次关系的顺序进行训练，每个模型都使用不同的训练数据进行训练。例如，顶层的模型1.1首先使用整个数据集进行训练。根据模型1.1的预测结果，选择模型2.1或2.2，并根据选择结果将整个数据集分为两个子数据集。第二阶段的两个模型使用各自的子数据集进行训练。下一阶段遵循类似的培训过程。