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

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

为未来的数据插入预留空间, 新数据可以直接在节点内部进行排序, 无需触发节点分裂, 减少了数据移动和分裂的
代价, 如图 3 所示.

Int_model Int_model Int_model Int_model
插入21 插入21
12 18 24 34 45 12 18 21 24 34 45 12 18 24 34 12 18 21 24 34
Leaf_model Leaf_model Leaf_model Leaf_model Leaf_model
(a) 传统的节点满后插入 (b) 设置节点阈值后插入
图 3 数据插入示意图

这一方法保证了与现有技术方法的一致性, 保留了现有的阈值分裂机制, 并在第 6.2.1 节根据本文的问题场景
进行了合适的阈值选择.
定义 12. 叶子关键值范围 LeafBound.
对每个叶子节点设置关键值数值区间:

[ ]
LeafBound = key min ,key max (17)
这是因为在范围查询过程中, 基于非均匀网格降维的一维值具有处于同一网格中的点前缀相似的特点, 所以
在形成对数据的约束条件之后, 需要遍历有序列表中所有前缀符合约束条件的键值, 这会导致冗余点也被纳入.
n
LeafBound 的设置可以直接通过核对区间值剔除查询冗余点, 有效避免了时间浪费. 上述定义中 key mi 是该节点中
最小查询键, key ma 是最大查询键, 在范围查询遍历过程中, 若叶子节点在粗过滤范围内, 则细化查询过程中先比
x
较 LeafBound 与实际查询区域 Bbox 是否存在包含或交叉关系, 若有则执行遍历, 若无则直接跳过当前叶节点, 有
利于提高范围查询效率.
4.2 非均匀网格学习索引结构设计
学习索引是一个具有层次结构的递归模型索引, 根据数据特点的需要选择对应的机器学习模型, 并将这些模
型组织成树形结构, 该树的分支数与深度均可自定义设置, 树的根节点中包含一个具有预测功能的学习模型, 通过
学习数据分布预测当前查询在哪一个孩子节点中, 然后跳至该预测节点, 迭代此过程直到进入叶子节点, 叶子节点
中存有最终的预测模型.
经典的学习索引为两层模型, 将数据集均匀划分为若干子集后使用机器学习模型学习数据分布, 但是两层模
型并不能支持高效的插入和更新, 因为模型需要重新学习插入新数据后的分布情况. 此外, 经典的 RMI 结构在使
用神经网络进行数据拟合时, 依靠全连接神经网络对输入的查询键进行学习, 并使用 ReLU 激活函数来进行非线
性的数据变换, 最后使用均方差作为损失函数, 但是这种做法会导致极大的模型训练代价, 在执行查询操作前需要
大量时间来训练模型. 而 FITing-Tree 的实现使用线性回归模型作为内部节点, 只需要存储线性回归模型的两个参
数: 斜率和截距, 降低了索引的存储开销, 且实验证明该索引的性能更优.
综合考虑上述问题, 为实现面向移动对象的高效查询, 提出了非均匀网格学习索引 NUGC_LI, 该索引模型的
结构如图 4 所示. 继承了经典学习索引的递归层次模型结构, 基于第 3 节中降维后的有序一维值进行索引, 且在数
据划分后, 降维数据的线性特征更为明显, 但使用神经网络来拟合数据间复杂的线性关系是较为困难的, 特别是当
神经网络规模小、数量多的时候. 因此选择使用多阶段的回归模型来取代需要多次训练的神经网络, 单调约束效
果更佳、所需参数更少、训练时间更短, 能够有效提高索引的构建效率.
第 1 部分的根节点有且仅有一个, 其内部存储了一个线性回归模型和一个指针数组指向孩子节点, 其中存储
线性回归模型即使用两个 64 位浮点数存储斜率和截距两个值, 另外还需要一个整数来记录误差值 err. 根节点下
连接的孩子节点个数必须是 2 的指数幂, 使用线性回归模型计算得到数组位置, 然后得到指向孩子节点的指针.
第 2 部分的内部节点同样包含线性回归模型和孩子指针数组, 并且每个子树的深度会因节点分裂的影响导致各不
相同, 因此节点中还需包含记录层数的整型值 level.