Page 328 - 《软件学报》2026年第5期

王撷阳 等: 基于数据分布的移动对象学习索引及查询算法 2207

工作负载而忽略了可变字符串键的问题, SIndex 使用共享前缀对键进行分组, 并使用每个键的唯一部分进行模型
训练, 有效降低了模型推理和数据访问的成本. Ding 等人 [35] 提出了一种基于内存可更新的学习型索引方法 ALEX.
ALEX 通过引入固定数据布局和就地插入策略, 解决了传统索引在动态插入操作中的效率问题. ALEX 采用自适
应的 RMI 结构, 能够处理新键的插入操作, 并且通过在初始化时执行根模型来对键空间进行分区. 每个非根节点
被分配一个固定数量的分区, 当分区大小合适时, 叶节点以间隙数组或压缩内存数组的形式创建以支持插入操作.
Ferragina 等人 [36] 提出了一个有最坏情况保证的学习型索引结构 PGM-index, 采用分段线性模型并通过增量缓冲
区插入策略支持动态更新. PGM-index 通过计算最优分段并递归构建, 实现了稳定的查询性能. Marcus 等人 [37] 将
RMI 与其他几种经典索引结构进行对比. 2021 年, Zhang 等人 [38] 提出了 CARMI (cache-aware recursive model
index) 索引, 固定每个节点大小, 确保数据查询的内存访问次数为最小最优值, 有效提升查询效率的同时, 具有更
相似的空间使用量. 同年, Wu 等人 [39] 提出了一种精确的键到位置映射学习索引 LIPP, 通过避免误预测后的局部
搜索来提升查询性能, 其核心在于采用核化线性模型确保映射均匀分布, 并利用最快最小冲突度算法 (fastest
minimum conflict degree, FMCD) 优化冲突处理. 与 ALEX 相似, LIPP 也采用了就地插入策略, 在动态数据更新时
展现出高效性. 2023 年, Li 等人 [40] 利用线性回归模型构建了一种基于数据分布的索引结构 DILI, 保证了动态数据
分布下的高效就地插入.
1.2.2 多维学习索引
多维学习索引与一维学习索引最大的不同在于排序难度显著提升. 在一维学习索引中, 只有单一的属性值, 可
以简单地对数据对象进行排序, 但多维数据存在逻辑顺序不强的问题, 这会影响学习模型对查找键预测的准确性.
现有的多维学习索引可以划分为: 映射一维、网格划分以及自定义布局. 在一维学习索引已经奠定坚实基础的情
况下, 研究者们认为对于多维数据的处理同样可以先转化为一维数据, 在此一维序列上建立学习索引, 根据索引预
测值在多维数据的误差范围内展开搜索.
2019 年, Wang 等人 [41] 提出了 ZM 索引, 借助 Z-order 空间填充曲线对移动对象数据进行降维, 并得到与空间
位置关系相关的有序数列, 构建机器学习模型来学习数据分布, 预测查询键位置. ZM 索引有效提升了查询效率和
存储占用率, 但其在实现查询过程中会对大量冗余点执行操作. 为解决这一问题, 2020 年, Davitkova 等人 [42] 提出
了多维度学习 (multidimensional learned, ML) 索引, 由两个重要组件组成, 首先是索引构建, 使用聚类算法得到参
考点, 基于距离函数和参考点将数据点降至一维, 得到排列后的一维值; 然后使用递归层次模型中的线性回归模型
对排列后的一维值分布进行学习. 实验证明, 此方法在范围查询时具有优势. 2022 年, Wang 等人 [43] 基于动态框架
提出时空跳跃连接模型 (spatio-temporal skip-connection model, STSM), 将时间和空间信息正确地结合起来. STSM
中包含时间模块和空间模块, 以及一个跳跃连接到原始输入融合时间、空间和全球信息的数据. 对比实验结果表
明, STSM 不仅优于单独的时间或空间模块, 而且比其他传统方法预测更准确.
将多维数据映射为一维的方法, 舍弃了部分空间特征, 为解决这一问题, 产生了网格划分多维数据的方法.
2020 年, Ding 等人 [44] 在 Flood 基础上提出了 Tsunami 索引, Tsunami 在构造的网格树的各分支中, 构造增强网格
对与该分支区域内相关的查询操作进行性能优化. 2021 年, Zhang 等人 [45] 提出了基于网格索引的空间插值函数
(spatial interpolation function based grid index, SPRIG), 采用了最近点剪枝技术和基于枢轴的过滤来提高最近邻问
题的查询性能, 通过在真实的数据集上实验得到, SPRIG 在查询时所用时间比 ZM 索引高出一个数量级, 在索引建
立、范围查询和 KNN 查询方面分别比 Flood 快 2.7 倍、3 倍和 9 倍, 但是消耗的空间更多.
虽然上述方法在查询时间和空间成本上都进行了一系列的优化, 但都不支持插入, 索引插入的位置将直接影
响查询性能. 自定义数据布局的含义是在初始多维数据的基础上, 更改数据的布局, 以解决索引插入的问题.
2020 年, Li 等人 [46] 提出了 LISA (learned index structure for spatial data), 在外存中将任意数据集布局为可查询状态,
LISA 使用机器学习模型建立可支持动态更新的数据布局, 实现了数据更新、插入和删除功能. 同时, 其还支持范
围查询, 并结合范围查询实现了最近邻查询, 通过实验可知, LISA 的 I/O 消耗仅为 R 树的 80% 左右, 同时占用磁
盘存储空间仅为 R 树的 90%. 与 LISA 相似, Qi 等人 [47] 同年提出一个基于磁盘的可更新学习型空间索引 RSMI, 支