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

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

索引的更新操作是需要对某索引数据进行修改, 存在两种可能的情况, 一种是虽然该数据记录和索引需要重
新赋值, 但是更新前后的变化较小, 并未影响到数组的有序排列, 在这种情况下仅需修改对应的数组元素, 不需要
进行其他操作; 另一种是该数据的更新会打破当前数组的有序性, 这种情况就需要进行删除旧键和插入新键的组
合操作, 首先通过查询操作找到需要更新的索引位置, 与其前后元素比较, 若更新值将破坏当前的有序性, 则将当
前位置的索引值和对应的数据记录清空, 然后再次执行查询操作, 找到待更新值应插入的位置, 执行插入操作, 具
体插入步骤可见第 4.4 节.

5 基于非均匀网格索引的查询算法

移动对象数据在支持位置服务的若干应用场景下, 主要的功能作用是为用户提供相关的查询服务, 因此基于
学习索引 NUGC_LI 提出高效的查询处理技术也是重要研究内容. 本节介绍基于 NUGC_LI 的范围查询、最近邻
查询和相似轨迹处理技术, 并通过实验验证了它们的有效性与实用性.
5.1 基于非均匀网格的范围查询

在现有面向移动对象的范围查询工作中, 查询区域通常被设置为矩形或圆形窗口, 通过经纬度信息查找通过
该范围的所有移动对象, 并保证该区域中生成的移动对象的时间戳也在查找时间间隔内, 最终将查询结果返回输
出. 例如, 通过将用户地理位置输入具有位置感知能力的应用程序中, 查询用户可以找到的附近相关的兴趣点, 如
便利店等, 如算法 3 所述.
基于 NUGC_LI 的范围查询, 首先根据查询区域的范围边界值查找得到最小值所在的叶子节点; 然后依次扫
描直到查询到范围的最大值. 在叶子节点的遍历过程中, 使用 bitmap 来跳过数组中的空元素, 如果查询范围较大
涉及多个叶子节点, 则使用叶子节点间的指针直接完成跳转.
学习索引的引入使得范围查询在定位查询边界所在的叶子节点时, 有效减少了搜索时间, 叶子关键值范围
LeafBound 的设置也避免了对冗余节点的遍历, 弥补了 NUGC 的不足, 叶子节点间的指针连接使得范围查询在确
定最小值所在节点之后能够直接跳至下一叶子节点, 顺序遍历有序数列, 无需再通过父节点进行跳转, 显著提升了
查询效率. 在后续实验部分将与传统索引和经典学习索引进行对比, 凸显基于 NUGC_LI 的范围查询的效率优势.

算法 3. 基于 NUGC_LI 的空间范围查询 RangeMO.
输入: 查询域对角点 ss, 查询域对角点 se, 学习索引 NUGC_LI;
输出: 符合范围查询条件的移动对象集合 Res.

1. Res ← ∅
2. ss ← NUGC(ss)
′
3. se ← NUGC(se)
′
4. prefix ← GetCommonPrefix(ss , se )
′
′
5. SearchRange ← get(prefix)
6. N ← GetRoot(NUGC_LI)
7. if N 是空节点 then
8. return Res
9. else

10. P ← NUGC_LI.Pointer(N)
11. 根据 SearchRange 查询叶子节点, 更新 P
12. P ← NUGC_LI.Pointer(min(SearchRange))
13. while P , null do
14. if Intersect(P.LeafBound, SearchRange) then /*通过叶子关键值范围判断是否需要遍历叶子节点*/