(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210819216.5 (22)申请日 2022.07.12 (71)申请人 南京邮电大 学 地址 210003 江苏省南京市栖霞区仙林街 道亚东新城区文苑路9号南京邮电大 学 (72)发明人 高隽　陈珊珊　 (74)专利代理 机构 湖北唯迈知识产权代理事务 所(普通合伙) 42314 专利代理师 王继云 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/23(2019.01) G06K 9/62(2022.01) (54)发明名称 一种利用梯度下降的学习索引 (57)摘要 本发明公开了一种利用梯度下降的学习索 引模型， 属于数据库优化领域， 主要解决的数据 库索引随着数据量爆炸式增加， 空间和时间开销 越来越大的问题， 提升数据库数据查询的速度和 减少索引结构的空间开销。 具体实现的步骤包 括： (1)将数据空间划分为多个子空间， 子空间之 间无重叠； (2)根据划分的子空间训练对应的拟 合函数； (3)递归调用数据划分算法和数据拟合 算法构建上层结构； (4)利用链表结构解决数据 插入问题。 本发 明利用机器学习模 型拟合数据分 布规律， 来代替传统数据库索引结构。 利用了机 器学习技术学习数据潜在的分布规律构建索引 模型， 可以大大减少索引结构的空间开销和查询 时的时间消耗。 权利要求书1页 说明书3页 附图2页 CN 115129721 A 2022.09.30 CN 115129721 A 1.一种利用梯度下降的学习索引模型， 包括了如下步骤： (1)对数据集进行划分， 使每个划分所得的子数据集中的数据无重叠部分， 且子数据集 中的数据分布尽可能一 致； (2)利用每 个子数据集中的数据分布规 律构建每 个子数据集对应的线段模型； (3)递归调用数据划分算法和数据拟合 算法， 构建上层结构； (4)利用链 表结构存 储新插入的数据。 2.根据权利要求1所述的学习索引模型， 其特征在于： 所述步骤(1)的具体实现方式为： 利用余弦相似度对数据集进行划分， 将分布在同一条线段附近的数据划分在同一个子数据 集中， 并且子数据集之间保证无 数据重复。 3.根据权利要求1所述的学习索引模型， 其特征在于： 所述步骤(2)的具体实现方式为： 在每个子数据集中调用梯度下降算法， 训练子数据集对应的线段模型， 使其损失函数值尽 可能的小。 4.根据权利要求1所述的学习索引模型， 其特征在于： 所述步骤(3)的具体实现方式为： 在步骤(2)中所有模型训练完 毕之后， 提取底层每个模型所覆盖的第一个数据， 产生一个新 的数据集， 然后在该数据集上递归调用数据划分算法和数据拟合算法， 形成上层 模型， 然后 在每一层模型 上递归此操作直至最后只产生 一个模型， 最后作为 最上层。 5.根据权利要求1所述的学习索引模型， 其特征在于： 所述步骤(4)的具体实现方式为： 根据模型计算出新插入的数据应该存放的位置， 然后根据位置的状态进行不同的操作， 若 位置为空则直接插入， 若不为空， 则将新插入的数据存放到对应的链表中， 并且链表中数据 保持有序。权　利　要　求　书 1/1 页 2 CN 115129721 A 2一种利用梯度下降的学习索引 技术领域 [0001]本发明属于数据库索引领域， 涉及利用机器学习优化传统索引的技术， 具体涉及 一种利用梯度下降算法拟合数据的索引优化方法。 背景技术 [0002]索引是数据库中提升数据读取性能的技术之一。 在传统索引技术中基于树结构的 索引运用最为广泛， 它们通过将数据的键组织成一棵树而减少查询的次数， 从而提高查询 的速度， 但随着数据量的不断增加， 树的体积会越来越大。 所以近几年来， 研究人员也通过 各种不同的方式减少索引的结构大小， 例如前/后缀截断、 哈夫曼编码等技术。 但是这些方 式随着数据量的爆发式增加也 失去了效果， 因为数据量的暴增， 不仅键的数量会增加， 同时 键本身的长度也会增加， 从而导致传统索引的开销也 随之线性增加。 由于最近几年人工智 能和数据库得到了广泛地研究， 进而有研究人员将人工智能和数据库结合起来， 利用人工 智能技术解决传统数据库无法满足大规模数据库实例等问题。 而索引就是其中一个方面， 近年有人提出了 “学习索引 ”的概念， 将机器学习引入索引技术， 有效地解决了索引空间开 销问题， 同时也 提高了查询性能。 [0003]学习索引通过机器学习技术学习数据分布规律， 通过模型拟合数据， 将传统索引 的间接查询优化为函数计算的直接查询， 从而使查询的效率要优于B+树等传统索引的性 能。 而且， 学习索引只需要存储模型 的参数即可， 所以在空间代价上， 学习索引也要优于传 统索引。 [0004]但是当前的学习索引还 存在许多问题， 如下： [0005](1)拟合效果差： 目前大多数学习索引模型都是通过欧几里得距离作为相似度进 行数据划分， 但是欧几里得距离体现的是个体数值的绝对差异， 多用于需要从维度的数值 大小中体现差异的分析中； 而对于学习索引中的数据拟合， 更多的是需要把在同一条线段 附近的数据划分在一起， 其中更重要的是方向上的差异， 所以这导致线 段拟合误差较大， 从 而导致进行本地搜索的时候 花费更多的时间。 [0006](2)上层结构开销大： 大多数现有学习索引模型的上层结构还是使用常见的数据 结构组织， 例如树、 哈希表等， 这些传统的数据结构的最大缺点就是它们的空间开销还是会 随着数据量的暴增而增大， 进而导致整个索引结构依旧会有很大 的空间开销， 降低了查询 性能。 [0007](3)不支持插入： 因为大量新数据的插入会破坏数据分布规律， 导致模型失效， 从 而要重新训练模型， 而模型重训练的成本是很大的， 所以学习索引模型只针对静态数据。 发明内容 [0008]针对现有技术存在的问题和改进需求， 本发明提供了一种利用梯度下降算法的学 习索引模型， 该模型先利用余弦相似度进行数据划分， 再利用梯度下降算法更好地拟合数 据， 减少拟合误差， 缩短本地查找的时间， 同时递归调用数据划分算法和数据拟合算法， 充说　明　书 1/3 页 3 CN 115129721 A 3