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

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

15. for each iter ← 0 to L(keyarray) do
16. if bitmap[iter] = 1 then /*通过 bitmap 跳过空元素*/
17. if keyarray[iter] then 在查询范围内
18. Res ← keyarray[iter] 指向的所有数据点
19. else if keyarray[iter] > max(SearchRange) then
20. return Res
21. 移动至下个叶子节点并更新 P
22. return Res
5.2 基于非均匀网格的最近邻查询

面向移动对象的最近邻查询则更为关注具有时间依赖性的最近邻查询研究, 如最快到达的出租车. 基于
NUGC_LI 的最近邻查询算法是移动对象数据库中较为重要的查询操作之一, 需要查找与指定对象距离最近的移
动对象.
最近邻查询在数据库的实际应用中还有一个重要变体, 即 k 近邻查询, 它的含义是连续查找 k 个距离指定对
象最近的移动对象. 在经典的最近邻查询算法中, 研究者们提出了大量类似于剪枝界定深度优先的算法, 希望通过
缩小搜索范围提高搜索效率. 但是, 所提出的最近邻查询算法与上述传统最近邻算法相比存在明显优势, 因为存储
的一维值由基于位置关系的 NUGC 算法生成, 所以对查询点的搜索区域可以限定在指定网格中, 而学习索引
NUGC_LI 的引入使得对于网格的查询时间有效降低, 如算法 4 所示.

算法 4. 基于 NUGC_LI 的最近邻查询 NNMO.
输入: 查询点 Q, 学习索引 NUGC_LI;
输出: 符合范围查询条件的移动对象集合 Res.

1. Res ← ∅
2. SearchQ ← NUGC(Q) /*对查询点进行降维, 得到降维后一维网格编码*/
3. N ← GetRoot(NUGC_LI)
4. if N 是空节点 then
5. return Res
6. else
7. P ← NUGC_LI.Pointer(N)
8. 根据 SearchQ 查询到对应叶子节点更新 P
9. P ← NUGC_LI.Pointer(SearchQ)
10. 遍历 SearchQ 网格中所有移动对象点
11. Q min ← MinDistance(Q,网格中任意点)
12. 根据指针 P 找到相邻的网格
13. for each iter ← 1 to 相邻网格数量 do
14. Distance(Q, 相邻网格中任意点)
15. if Distance.value < MinDistance.value then
16. 更新 Q min
17. Res ← Q min
18. return Res

算法 4 实现的最近邻算法同样为“粗过滤−细筛查”的二阶段查询过程, 首先在进行非均匀网格降维的基础上,