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

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

较 B+树索引降低至少 71.52%, 较 RMI 索引降低至少 20.19%, 较 3DR 树索引降低至少 64.39%, 较 TB 树索引降低
至少 63.92%. 可见除 ALEX 索引外, 无论 k 取何值, NUGC_LI 索引都具有明显优势, 且在不同数据集中查询性能
都十分稳定. 相比于 ALEX 索引, NUGC_LI 索引在 k 为 1 时, 在深圳市数据集和随机数据集上表现相当, 但随着 k
值增大, NUGC_LI 索引优势逐渐增大, 查询时间分别最高降低 21.99% 和 16.06%.

B+树 3DR树 TB树 B+树 3DR树 TB树
RMI ALEX NUGC_LI 2 000 7 000 RMI ALEX NUGC_LI 2 500
B+树、3DR树、TB树查询时间 (s) 5 000 1 000 RMI、ALEX、NUGC_LI索引查询时间 (s) B+树、3DR树、TB树索引查询时间 (s) 5 000 1 500 RMI、ALEX、NUGC_LI索引查询时间 (s)
7 000
6 000
6 000
2 000
4 000
4 000
3 000
3 000
1 000
2 000
2 000
1 000
0
0 0 1 000 0 500
1 3 5 7 1 3 5 7
相似轨迹条数 相似轨迹条数
(a) 深圳市数据集 (b) 随机数据集
图 20 不同 k 值的相似轨迹查询时间对比图

7 总结与展望

以学习索引研究为出发点, 提出了基于空间位置关系的降维算法 NUGC、学习索引 NUGC_LI 以及 3 种应用
广泛的查询技术, 通过构建高效索引提升移动对象数据的查询效率, 支持移动对象数据的频繁更新, 以满足现实场
景下对于移动对象数据的处理任务需求, 提供更为快速、高效的查询服务. 但是对于移动对象数据库领域而言, 仍
然存在许多难题和挑战需要攻克, 学习索引在移动对象数据领域的应用还处于初步阶段, 并未在现实场景下被广
泛部署应用.

References
[1] Han SY, He Q, Yu ZQ, Tong XR, Zheng BL. Double layer index for continuous k-nearest neighbor queries on moving objects. Ruan Jian
Xue Bao/Journal of Software, 2023, 34(6): 2789–2803 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6492.htm
[doi: 10.13328/j.cnki.jos.006492]
[2] Antol M, Ol’ha J, Slanináková T, Dohnal V. Learned metric index—Proposition of learned indexing for unstructured data. Information
Systems, 2021, 100: 101774. [doi: 10.1016/j.is.2021.101774]
[3] Marcus R, Zhang E, Kraska T. CDFShop: Exploring and optimizing learned index structures. In: Proc. of the 2020 ACM SIGMOD Int’l
Conf. on Management of Data. Portland: ACM, 2020. 2789–2792. [doi: 10.1145/3318464.3384706]
[4] Cai P, Zhang SM, Liu PR, Sun LM, Li CP, Chen H. An overview of learned index technologies for intelligent database. Chinese Journal
of Computers, 2023, 46(1): 51–69 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2023.00051]
[5] Chai MK, Fan J, Du XY. Learnable database systems: Challenges and opportunities. Ruan Jian Xue Bao/Journal of Software, 2020,
31(3): 806–830 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5908.htm [doi: 10.13328/j.cnki.jos.005908]
[6] Li GL, Zhou XH, Sun J, Yu X, Yuan HT, Liu JB, Han Y. A survey of machine learning based database techniques. Chinese Journal of
Computers, 2020, 43(11): 2019–2049 (in Chinese with English abstract). [doi: 10.11897/SP.J.1016.2020.02019]
[7] Chao C, Pu FF, Xu JQ, Gao YJ. Efficient dimensionality reduction and query algorithm of trajectory data based on spatial position
relation. Journal of Computer Research and Development, 2024, 61(7): 1771–1790 (in Chinese with English abstract). [doi: 10.7544/
issn1000-1239.202330609]
[8] Tong YX, She JY, Ding BL, Wang LB, Chen L. Online mobile micro-task allocation in spatial crowdsourcing. In: Proc. of the 32nd IEEE
Int’l Conf. on Data Engineering. Helsinki: IEEE, 2016. 49–60. [doi: 10.1109/ICDE.2016.7498228]
[9] Tong YX, Pan XC, Zeng YX, Shi YX, Xue CB, Zhou ZM, Zhang XF, Chen L, Xu Y, Xu K, Lv WF. Hu-Fu: Efficient and secure spatial