论文部分内容阅读
索引结构是用来提高数据访问性能的重要工具，但其采用的数据结构没有考虑真实数据的分布特征。而机器学习的本质是从数据中发掘隐藏的模式，这些从数据中发掘的模式反映了数据的内在联系和分布规律。因此机器学习为建立数据索引提供全新的解决思路。此外，机器学习模型存储空间小、并行度高、查询速度快的特点可以有效地提高索引的查询性能，降低索引带来的空间开销。然而目前基于机器学习的索引结构（简称学习索引）存在着以下不足：1）从多个维度构建主键索引时，学习索引带来的误差范围很高，查询开销急剧增长；2）只适用于聚簇索引，不能应用于二级索引的场景。本文针对学习索引存在的不足，对基于机器学习的数据索引技术进行深入研究。
首先，针对学习索引在多维数据上误差范围过大的问题，通过深入分析索引问题的特点和需求，本文提出了一种递归提升模型索引结构Recursive Boosting Model Index（简称B-RMI）。在模型分层结构的设计下，本文通过三个方面进行结构的优化：自顶向下拟合预测残差来充分利用非叶子模型的拟合效果、权重更新来提高对离群数据的关注度和预设阈值进行数据剪枝，从而提高整体索引结构的预测准确度。
其次，针对学习索引不适用于二级索引的局限性问题，本文提出了一种两阶段二级索引模型结构。其中第一阶段通过二分类模型和Bloom Filter进行两步筛选，将数据划分成唯一键值和非唯一键值，并保有一定的误判率。然后在第二阶段根据两类数据的特点，分别构建索引模型进行处理，从而满足二级索引的查询要求。
最后，基于上述两个理论成果，本文先通过合成数据和 OpenStreetMap 真实地点数据对B-RMI、RMI和B-Tree结构性能进行比较分析，表明B-RMI结构在多维数据上的预测准确度有显著提升。然后通过开源NYC出租车数据、基准测试工具TPC-D生成的不同倾斜度订单数据和Instacart 商店数据，对两阶段二级索引结构和 B-Tree二级索引性能进行比较分析，表明该结构在提高查询效率和降低内存开销上的优势。最终验证了本文研究工作的可行性和有效性。
首先，针对学习索引在多维数据上误差范围过大的问题，通过深入分析索引问题的特点和需求，本文提出了一种递归提升模型索引结构Recursive Boosting Model Index（简称B-RMI）。在模型分层结构的设计下，本文通过三个方面进行结构的优化：自顶向下拟合预测残差来充分利用非叶子模型的拟合效果、权重更新来提高对离群数据的关注度和预设阈值进行数据剪枝，从而提高整体索引结构的预测准确度。
其次，针对学习索引不适用于二级索引的局限性问题，本文提出了一种两阶段二级索引模型结构。其中第一阶段通过二分类模型和Bloom Filter进行两步筛选，将数据划分成唯一键值和非唯一键值，并保有一定的误判率。然后在第二阶段根据两类数据的特点，分别构建索引模型进行处理，从而满足二级索引的查询要求。
最后，基于上述两个理论成果，本文先通过合成数据和 OpenStreetMap 真实地点数据对B-RMI、RMI和B-Tree结构性能进行比较分析，表明B-RMI结构在多维数据上的预测准确度有显著提升。然后通过开源NYC出租车数据、基准测试工具TPC-D生成的不同倾斜度订单数据和Instacart 商店数据，对两阶段二级索引结构和 B-Tree二级索引性能进行比较分析，表明该结构在提高查询效率和降低内存开销上的优势。最终验证了本文研究工作的可行性和有效性。