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

2204 软件学报 2026 年第 37 卷第 5 期

习模型, 并非通过遍历查询数据, 而是通过训练得到模型, 模型根据输入值得到预测位置, 学习索引在以预测位置

为中心的误差区间内进行遍历查询, 将查询的时间复杂度从原本的 O(logn), 降低为 O(C); 索引文件的空间成本降
低, 传统索引在存储时通常以文件形式存储, 但是对于学习索引的叶子节点只需要存储模型参数, 将存储的空间复
O(C); 针对现有学习索引缺少高效更新机制的问题, 设计与研究了针对移动对象学习索引的
杂度从 O(n), 降低为
插入更新机制, 提高索引的可扩展性.
(3) 学习索引可应用于多种移动对象查询, 实用性高. 针对所提出的学习索引, 实现了在移动对象查询领域应
用最为广泛的范围查询、最近邻查询和相似轨迹查询算法, 以验证学习索引在查询应用中的准确性和高效性, 同
时提高移动对象学习索引的实用性.
高效的降维算法和学习索引的设计与研究, 对于优化移动对象数据库中的查询操作具有十分重要的现实意
义, 可以应用到数据量庞大且响应速度要求较高的位置服务领域中, 有利于提高移动对象数据库的管理能力. 考虑
传统的索引结构在处理海量复杂的移动对象时存在较大难度, 而基于机器学习模型构建的学习索引, 能够充分学
习移动对象数据和存储位置的关系, 训练后的模型在查询性能和存储成本上优于传统的索引结构, 体现了数据分
布的特点. 目前已有的学习索引多是针对基于单个机器学习模型而构建 [3] , 存在功能局限性, 因此本研究根据移动
对象数据分布特点与数据库查询操作要求, 构建适应大规模移动对象数据集、在更低的空间占用下实现更高查询
性能的学习索引. 研究工作概括如下.
(1) 设计基于移动对象数据\空间位置关系的均匀网格编码 (uniform grid code, UGC) 算法, 提出具有数据分布
感知的降维算法, 即根据数据分布优化网格布局, 称为非均匀网格降维算法 (non-uniform grid code algorithm,
NUGC), 从而支持非均匀数据分布优化存储空间, 在压缩移动对象数据存储空间的同时充分保留其空间位置关系
的特点, 通过非均匀网格降维得到的一维值为学习索引构建和查询研究提供数据基础.
(2) 提出基于空间位置关系降维的一维非均匀网格学习索引 (non-uniform grid code learned index, NUGC_LI),
该索引结构为递归层次模型, 含根节点、内部节点和叶子节点这 3 部分, 每个节点均含有线性回归模型, 将查询输
入值转化为数据位置的预测值, 并在预测值的误差范围内展开搜索. 移动对象数据具有动态更新的特点, 因而对设
计的学习索引制定插入更新机制, 使其具备支持历史数据插入、删除的功能. 同时, NUGC_LI 支持节点的动态分
裂, 能够更好地满足移动对象的更新需求.
(3) 设计移动对象数据查询领域应用较为广泛的查询算法, 实现使用学习索引对移动数据进行查询的算法研
究, 并测试查询操作的效率与准确率, 在不同查询场景下将非均匀网格学习索引和传统索引、经典学习索引进行
性能对比, 分别在真实采集轨迹数据、模拟仿真轨迹数据和随机生成轨迹数据等不同数据集上验证其性能优势.
综上所述, 本研究旨在通过构建学习索引提高移动对象数据的查询效率. 基于真实的全球定位系统 (global
positioning system, GPS) 得到采集数据, 对多维数据进行数据准备和基于位置的降维处理, 然后利用机器学习模型
及时学习和更新能力的特点, 构造出能够提高查询性能、降低空间占用的学习索引结构. 该索引根据查询参数直
接确定查询结果所在数据块, 避免中间节点的访问, 并对参数调优以适应数据特点与任务需求.

1 相关工作

国内外针对移动对象数据的研究已发展多年, 取得了丰富的研究成果. 空间索引作为移动对象数据库的重要
组成部分, 被国内外学者广泛研究, 很多通用高效的索引算法被相继提出. 但是随着目前物联网技术和智能应用的
不断发展, 各种新型数据不断涌现, 新型索引和查询算法需要适应新应用下用户的需求. 尤其是在现实应用场景下
要求系统能够在海量数据中迅速找到对用户有用的信息, 要求实现的索引及查询操作更具通用性, 这也要求针对
移动对象数据索引及查询的研究工作能够更加深入并不断创新 [4,5] .
学习索引利用机器学习模型, 输入查询键值, 预测相应数据记录存储位置. 由于学习索引对模型进行训练以反
映数据模式的相关性, 数据需具备有序性, 所以目前的研究趋势仍以一维数据为主, 对于多维空间数据的学习索引
建立则是先通过降维算法将多维数据转化为一维数据, 再使用机器学习方法进行处理 [6,7] .