Page 323 - 《软件学报》2026年第5期
P. 323
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(5):2202−2234 [doi: 10.13328/j.cnki.jos.007483] [CSTR: 32375.14.jos.007483] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
*
基于数据分布的移动对象学习索引及查询算法
王撷阳 1 , 巢 成 1 , 金 鑫 1 , 许建秋 1 , 高云君 2
1
(南京航空航天大学 计算机科学与技术学院/软件学院, 江苏 南京 211106)
2
(浙江大学 计算机科学与技术学院, 浙江 杭州 310058)
通信作者: 许建秋, E-mail: jianqiu@nuaa.edu.cn
摘 要: 移动对象的来源丰富、获取简单、运动频繁, 导致数据量呈现爆发式增长, 高效管理移动对象数据的需求
日益增加, 使得移动对象数据的索引及查询成为亟待解决的热点问题. 传统的移动对象索引基于空间划分, 能够有
效地处理对象的空间位置和时间变化, 但由于移动对象的动态特性需要频繁更新索引, 在对象数量庞大时会导致
维护成本显著增加. 学习索引作为新型索引技术, 可以运用机器学习方法提高查询效率, 降低存储成本, 但学习索
引并不适用于具有多维特性的移动对象数据. 为此, 提出了一种基于非均匀网格降维的学习索引 NUGC_LI, 使用
类似 B+树的递归层次模型结构. 该学习索引分为根节点、内部节点和叶子节点这 3 个部分, 使用多阶段线性模型
对灵活划分后的数据分布进行拟合学习, 并在叶子节点中设置有空隙的数组和节点关键值范围, 提高节点更新和
查询效率. 同时, 对真实出租车轨迹、系统仿真火车轨迹和随机生成轨迹数据集分别建立了 B+树、RMI、ALEX、
NUGC_LI、3DR 树与 TB 树索引. 真实数据集、仿真数据集和随机数据集中涉及的轨迹点分别约 917 000 个、
51 544 个和 5 222 752 个. 通过对比实验与伸缩性测试, 在索引构建上, 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 索引在多任务负载下不仅具备较高的扩展性, 而且在构建、更新以及查询操作中均实现了显著
的性能提升.
关键词: 学习索引; 机器学习; 非均匀网格; 查询算法; 移动对象
中图法分类号: TP311
中文引用格式: 王撷阳, 巢成, 金鑫, 许建秋, 高云君. 基于数据分布的移动对象学习索引及查询算法. 软件学报, 2026, 37(5): 2202–2234.
http://www.jos.org.cn/1000-9825/7483.htm
英文引用格式: Wang XY, Chao C, Jin X, Xu JQ, Gao YJ. Moving Object Learned Index and Query Algorithm Based on Data
Distribution. Ruan Jian Xue Bao/Journal of Software, 2026, 37(5): 2202–2234 (in Chinese). http://www.jos.org.cn/1000-9825/7483.htm
Moving Object Learned Index and Query Algorithm Based on Data Distribution
1
1
1
1
WANG Xie-Yang , CHAO Cheng , JIN Xin , XU Jian-Qiu , GAO Yun-Jun 2
1
(College of Computer Science and Technology/College of Software, Nanjing University of Aeronautics and Astronautics, Nanjing 211106,
China)
2
(College of Computer Science and Technology, Zhejiang University, Hangzhou 310058, China)
Abstract: The abundance of sources, ease of acquisition, and frequent movement of moving objects have led to exponential growth in
data volume. The growing need for efficient management of moving object data has made indexing and querying such data a pressing
* 基金项目: 国家自然科学基金 (62472217, U23A20296)
收稿时间: 2024-11-28; 修改时间: 2025-04-02; 采用时间: 2025-06-06; jos 在线出版时间: 2025-10-29
CNKI 网络首发时间: 2025-10-31
