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

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

因为移动对象往往包含多个位置点, 尤其是时间周期长的对象, 所以时间复杂度 O(M) 代价依然很高. 例如,
采样频率为 10 s, 一天的移动对象具有 M=8640 个位置点. 为此, 设计了两种优化方法: (1) 前缀编码分组; (2) 子轨
迹估计表示. 采用前缀编码分组使得所有移动对象点根据前 5 次二分后所在网格的编码前缀被分配到不同的数组
中. 通过数组规模判断聚集程度高或低的网格, 避免遍历密度显著高于密度阈值的分组, 降低访问开销. 子轨迹估
计表示通过最小矩形框 Bbox 表示时空范围, 通过不同时间区间划分, 用 Bbox 的中心点代表指定区间内的所有数

据点, 减少移动对象点数量, 将时间复杂度从 O(M) 降低到 O(M/m), 其中 m 是子轨迹 Bbox 中含轨迹点数量的平均值.
4 非均匀网格学习索引

学习索引的核心理念在于索引不再是静态的数据结构或文本文件, 而是一个可以预测查询键位置的机器学习
模型, 模型可以被训练, 因而数据库索引也可以被训练和学习. 但是现有的学习索引多面向静态只读数据或一维数
据, 本工作所构建的非均匀网格降维学习索引面向移动对象, 基于通过 NUGC 降维后的值进行查询键预测. 同时,
考虑到移动对象位置的更新特点, 如果使用传统的学习索引, 每插入新的位置数据就需要重新训练索引模型, 会导
致查询成本显著提高, 因此 NUGC_LI 还支持插入、更新和删除操作. 为应对数据更新与新增数据引起的冲突, 节
点内预留了足够的空隙, 并设定节点阈值, 以便在数据插入时能够直接在预测位置附近进行微调, 减少因全局重训
练带来的开销. 采用局部数据平移以及扩展分裂两种策略, 以避免每一次数据更新时都进行大范围的模型重训练,
从而降低更新成本, 提高索引的实时性. 基于预测位置误差控制方法, 确保更新过程中的查询准确性, 并通过统计
误差信息动态调整节点分裂策略, 从而兼顾高效查询和低更新延迟, 能够初步满足在线场景的需求.
4.1 相关定义
定义 9. 误差区间 ErrINR.

ErrINR = [PrePos−err,PrePos+err] (14)
其中, PrePos 为学习索引预测的查询值所在数组中的位置, err 为误差值, 每次通过学习索引预测到查询值的位置
后, 在误差区间内用二分查找算法进行遍历搜索, 以保证查询准确性.
定义 10. 非均匀网格学习索引 NUGC_LI.
NUGC_LI 学习索引由 3 部分模型组成, 第 1 部分由一个线性回归模型构成的根节点模型; 第 2 部分是若干个
可扩展的内部节点, 每个节点中存在一个线性回归模型; 第 3 部分是叶子节点, 也可以被视为数据节点模型.

{ }
NUGC_LI = Root model , Expandable Int model , Leaf (15)
model
指定一个查询键, NUGC_LI 中的第 1 部分是一个回归模型用来预测下一部分应选择哪个子模型, 第 2 部分的
所有内部节点都是回归子模型, 用来预测符合查询键所在范围的叶子节点, 第 3 部分是叶子节点用来预测有序数
组中查询键所在的准确位置. 这 3 层模型均是选择适应数据分布的机器学习模型, 通过数据训练得到较高的预测
准确率.
定义 11. 学习索引节点阈值 NodeTHR.
因为学习索引支持数据插入及更新, 所以为每个节点设置节点阈值, 当该节点中包含的数据位置信息已经超
过阈值, 则该节点模型需要进行分裂, 分裂机制见第 4.4 节索引插入机制. 节点阈值计算公式如下:

M
NodeTHR = ×X, X ∈ (0,1) (16)
Count(LR leaf )
其中, M 为移动对象点个数, 即查询数据集中对象总数, LR lea 是作为叶子节点的回归模型, Count(LR leaf ) 则是作为
f
叶子节点的回归模型的个数. 同时, 因为索引在更新和插入阶段, 为保持移动对象的空间位置关系会造成其他数据
的移动和存储位置变换, 键值及指针数组中需要保留一定的间隙空间, 因此需乘以一个变量 X 使得节点总是未被
完全插满, 为数据的移动操作提供空间.
在移动对象数据库中, 例如城市车辆位置跟踪的场景下, 数据需要频繁更新和插入. 传统索引结构在节点满时
通过分裂来适应新的数据插入, 在静态数据集上表现良好, 但在当前问题场景下, 调低阈值允许索引在构建阶段就