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

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

issue. Traditional moving object indexes, based on spatial partitioning, can effectively handle changes in the spatial position and temporal
dynamics of objects. However, due to the dynamic nature of moving objects, which require frequent index updates, maintaining these
indexes becomes costly with large datasets. Learned indexes, as an emerging indexing technique, have the potential to improve query
efficiency and reduce storage costs by leveraging machine learning methods. Nevertheless, learned indexes are not well-suited for data with
multidimensional characteristics. To address this limitation, the proposed learned index uses the non-uniform grid code algorithm
(NUGC_LI). It employs a recursive hierarchical model structure similar to the B+-tree, divided into root, internal, and leaf nodes. The
learned index uses a multi-phase linear model to adapt to the flexibly divided data distribution, setting arrays with gaps and node key
value ranges in the leaf nodes to improve node update and query efficiency. At the same time, B+-tree, RMI, ALEX, NUGC_LI, 3D R-
tree, and TB-tree indexes are constructed for real taxi trajectories, system simulation train trajectories, and randomly generated trajectory
datasets for comparison. The number of trajectory points in the real, simulated, and random datasets is approximately 917 000, 51 544, and
5 222 752, respectively. Through comparative experiments and scalability tests, NUGC_LI reduces the index construction time by
approximately 91.45%, 89.63%, 90.38%, 87.46%, and 13.71% compared to TB-tree, 3D R-tree, B+-tree, RMI, and ALEX, respectively.
For update operations, the update time is reduced by at least 93.76%. Range queries, nearest neighbor queries, and similar trajectory
queries based on NUGC_LI show significant advantages under large-scale data conditions, with query times reduced by at least 8.74%,
30%, and 16.07% compared to ALEX; 29.38%, 77.44%, and 25.24% compared to RMI; 52.72%, 92.44%, and 70.5% compared to B+-
tree; 53.09%, 91.2%, and 67.58% compared to 3D R-tree; and 52.67%, 90.43%, and 67.47% compared to TB-tree. The NUGC_LI index
not only demonstrates high scalability under multi-task loads but also achieves significant performance improvements in construction,
updates, and query operations.
Key words: learned index; machine learning; non-uniform grid; query algorithm; moving object
基于空间位置的应用服务已广泛融入日常生活的各个领域, 移动对象数据处理因此成为亟待解决的关键问
题. 随着物联网位置获取技术的持续发展, 研究者获取移动对象数据的方式变得日益简便. 例如, 微信朋友圈定位、
智能移动设备定位、出租车与公交车定位等应用需求 [1] 均是将移动对象在其移动过程中所记录的经纬度信息按
时间顺序排列, 形成一系列具有时间属性的多维坐标. 由于移动对象数据来源广泛、获取便捷且采集频率较高, 导
致数据呈现爆发式增长, 成为数据库领域的研究热点之一.
当数据增长的速度已经远超学习和处理的速度时, 数据量的存储将会趋于极限, 这就要求索引结构的设计能
够减少物理空间的占用量和存储成本, 同时能够充分保留移动对象数据的时空相似性. 近年来, 人工智能、机器学
习等技术迅猛发展, 数据库管理技术也随之发生变化, 研究学者越来越多地引入机器学习方法来构建学习索引 [2] ,
索引结构也不断被调整和扩展.
学习索引有效规避了传统索引中忽略数据的分布特性、树状索引结构深度过大、磁盘 I/O 冗余操作等缺陷,
将索引看作一种模型, 通过机器学习模型来拟合数据分布, 将查询键作为模型输入值, 通过预测可以返回查询键对
应记录所在的位置, 有效提高了查询效率、减小了索引文件的存储成本. 因此, 在传统索引结构的基础上, 引入学
习索引, 贴合实际应用场景, 优化索引的更新方法, 从而提升数据库查询的效率是十分必要的.
当前学习索引的应用对象仍以一维数据为主, 所以在面向移动对象构建学习索引之前, 应先对移动对象数据
进行降维处理. 数据降维是研究者们在处理和存储多维度数据时, 为解决其空间占用问题而提出的, 旨在将高维数
据映射到低维数据空间, 但是移动对象数据与其他多维数据相比, 具有明显的空间特性, 如何在降维过程中充分保
留移动对象数据的空间位置特征仍是值得研究的问题.
移动定位技术和无线通讯技术的广泛应用, 使得移动对象数据的相关研究变得越发重要. 为了提高移动对象
复杂操作的效率, 节省数据存储的占用率和索引文件的更新频率, 开展了面向移动对象数据的学习索引与查询算
法研究, 其意义可以概括为以下 3 点.
(1) 对于海量移动对象数据的处理更加友好. 对移动对象数据进行基于空间位置关系的高效降维有利于在压
缩存储空间的同时保留位置特征. 索引构建时, 基于降维后数据的分布特点进行数据划分, 运用机器学习模型充分
学习数据的分布规律, 有效避免复杂的运算操作, 利用简单的线性回归模型直接预测需查找数据的位置.
(2) 有效提高查询操作的效率. 传统索引基于树的数据结构每次查询都需要从树的根节点开始遍历搜索, 直到
抵达叶节点, 找到数据存储的位置. 随着数据量的增大, 索引结构过深, 查询性能也随之降低. 但是学习索引使用学