软件学报

作者：王撷阳，巢成，金鑫，许建秋，高云君

单位：王撷阳，南京航空航天大学 计算机科学与技术学院/软件学院, 江苏 南京 21110611,巢成，南京航空航天大学 计算机科学与技术学院/软件学院, 江苏 南京 21110602,金鑫，南京航空航天大学 计算机科学与技术学院/软件学院, 江苏 南京 21110603,许建秋，南京航空航天大学 计算机科学与技术学院/软件学院, 江苏 南京 21110604,高云君，浙江大学 计算机科学与技术学院, 浙江 杭州 31005805

关键词：学习索引;机器学习;非均匀网格;查询算法;移动对象

基金：国家自然科学基金(62472217, U23A20296)

移动对象的来源丰富、获取简单、运动频繁, 导致数据量呈现爆发式增长, 高效管理移动对象数据的需求日益增加, 使得移动对象数据的索引及查询成为亟待解决的热点问题. 传统的移动对象索引基于空间划分, 能够有效地处理对象的空间位置和时间变化, 但由于移动对象的动态特性需要频繁更新索引, 在对象数量庞大时会导致维护成本显著增加. 学习索引作为新型索引技术, 可以运用机器学习方法提高查询效率, 降低存储成本, 但学习索引并不适用于具有多维特性的移动对象数据. 为此, 提出了一种基于非均匀网格降维的学习索引NUGC_LI, 使用类似B+树的递归层次模型结构. 该学习索引分为根节点、内部节点和叶子节点这3个部分, 使用多阶段线性模型对灵活划分后的数据分布进行拟合学习, 并在叶子节点中设置有空隙的数组和节点关键值范围, 提高节点更新和查询效率. 同时, 对真实出租车轨迹、系统仿真火车轨迹和随机生成轨迹数据集分别建立了B+树、RMI、ALEX、NUGC_LI、3DR树与TB树索引. 真实数据集、仿真数据集和随机数据集中涉及的轨迹点分别约917000个、51544个和5222752个. 通过对比实验与伸缩性测试, 在索引构建上, NUGC_LI相较于TB树、3DR树、B+树、RMI和ALEX分别降低了约91.45%、89.63%、90.38%、87.46%及13.71%的构建时间; 在更新操作上, 其更新时间降低至少93.76%. 基于NUGC_LI的范围查询、最近邻查询和相似轨迹查询在大数据量条件下均显示出显著优势, 查询时间分别至少比ALEX降低8.74%、30%和16.07%; 比RMI降低29.38%、77.44%和25.24%; 比B+树降低52.72%、92.44%和70.5%; 比3DR树降低53.09%、91.2%和67.58%; 比TB树降低52.67%、90.43%和67.47%. NUGC_LI索引在多任务负载下不仅具备较高的扩展性, 而且在构建、更新以及查询操作中均实现了显著的性能提升.

来源：2026年第5期

《软件学报》期刊编辑部

查看软件学报杂志2026年第5期