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

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

通过构建的学习索引 NUGC_LI 找到查询点 Q 对应单元格查询键所在的叶子节点, 并找到查询键位置, 其次通过
数据指针数组找到该单元格中包含移动对象点数组, 依次遍历并计算单元格中所有移动对象与查询点 Q 的欧氏
距离, 得到最近邻居, 若区域单元格数量为 1, 则寻找数据点的最近邻居, 否则在相邻单元格内的数据点继续搜索
可能的最近邻居, 最后结束遍历, 返回最近邻居点. 该算法支持向 k 近邻的扩展. 在细筛查阶段, 可将单一最小值比
较替换为可容纳 k 个元素的最大堆, 动态维护当前的前 k 个最近邻的候选集合. 当候选集合未满或相邻网格中存
在距离更近的潜在点时, 算法可基于当前第 k 近邻的距离阈值, 自动扩展搜索范围至更远层级的相邻网格, 直至满
足 k 个结果的覆盖性要求. 若某网格到查询点 Q 的最小距离大于距离阈值, 则可直接跳过该网格的遍历, 避免无
效计算.
5.3 基于非均匀网格的相似轨迹查询
由于移动对象数据模型与数据采集现状, 传统的轨迹相似性计算与分析一般基于移动对象位置点距离的不同
形式的组合, 割裂了移动对象位置点之间内在的连续性, 忽略了移动对象位置点之间的隐含的数据分布信息, 在比
较实际轨迹时, 通过计算整条轨迹的相似性可以得到一个相似度数值. 然而, 真实移动对象的轨迹通常具有不同的
长度, 时空起始点与终止点存在间隔, 采样频率与时长也各不相同, 整体相似性受轨迹跨越不同区域的影响较大.
经典轨迹相似性计算方法一般通过对时间翘曲或拉伸来实现采样点之间的匹配, 改变了移动对象数据的时空
特性, 并不利于轨迹相似情况的对比分析, 而非均匀网格编码方法能够反映出轨迹在不同粒度下的相似特性. 从大
量点距离的计算到基于连续有序段的字符串编码的匹配分析, 有效简化相似性度量步骤, 加快查询效率. 如算法 5
所示.
算法 5. 基于 NUGC_LI 的相似轨迹查询 NL-TSR.

输入: 查询轨迹 MP Q , 学习索引 NUGC_LI;
输出: 符合相似轨迹查询条件的移动对象集合 Res.

1. Res ← ∅
2. max_sim ← 0
3. 将 MP Q 中每个位置点转换为 NUGC 编码, 生成编码序列 Code_Q
4. N ← GetRoot(NUGC_LI)
5. if N 是空节点 then
6. return Res
7. else
8. P ← NUGC_LI.Pointer(N)
, null do
9. while P
10. for each 轨迹 Traj in P.LeafTrajs do /*遍历当前叶子节点存储的轨迹*/
Code_i ← Traj 的 NUGC_LI 编码
11.
12. 计算 Traj-StrSim(Code_Q, Code_i) /*基于定义 13 计算轨迹相似度*/
13. if Traj-StrSim(Code_Q, Code_i) > max_sim then
14. max_sim ← Traj-StrSim(Code_Q,Code_i)
15. Res ← Traj /*重置为当前最大相似轨迹*/
16. else if Traj-StrSim(Code_Q, Code_i) = max_sim then
17. Res ← Res∪Traj /*保留相同最大值的轨迹*/
18. 移动至下一叶子节点并更新 P
19. return Res

第 2.2 节的定义 7 和定义 8 中已经对轨迹相似性度量及查询进行了描述, 但是基于非均匀网格降维后的编码,