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

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

轨迹的相似性度量与查询均得到改进. 移动对象位置点的编码可以反映出空间邻近关系, 将相似轨迹查询从大量
点距离计算转化为简单的编码最长公共前缀匹配. 不同移动对象数据编码中的任意一对节点编码的相同前缀长度
代表着对应移动对象数据的相似程度.
定义 13. 基于 NUGC_LI 的轨迹相似性度量.
移动对象数据在降至一维后, 定义轨迹相似度:

MP-StrSim(MP 1 , MP 2 )
Traj-StrSim(MP 1 , MP 2 ) = (20)
length

∑ ∑
( )
StrSim(Loc i , MP 2 ) StrSim Loc j , MP 1
MP-StrSim(MP 1 , MP 2 ) = Loc i ∈MP 1 + Loc j ∈MP 2 (21)
2×n 2×n

StrSim(Loc, MP) = min Co-Prefix(Loc,P i ) (22)
P i ∈MP
其中, StrSim(Loc, MP) 为给定位置点 Loc 与移动对象 MP 的相似性度量, Co-Prefix(Loc,P i ) 为给定位置点 Loc 与
MP 中第 i 个点编码的最长公共前缀长度. MP-StrSim(MP 1 , MP 2 ) 是轨迹中所有给定点距离另一轨迹的相似性度
量, 即两条轨迹间的相似性度量, n 为每条轨迹中的代表点个数. Traj-StrSim(MP 1 , MP 2 ) 则是对轨迹间的相似性度
量值进行归一化处理, length 为初始编码长度. 从公式 (20) 易知 Traj-StrSim(MP 1 , MP 2 ) ∈ [0,1], 且值越大, 轨迹相似
性程度越高.
定义 14. 基于 NUGC_LI 的轨迹相似性查询 NL-TSR.
提出的轨迹相似性查询基于非均匀网格降维编码, 并在编码上构建学习索引 NUGC_LI, 基于 NUGC_LI 的轨
迹相似性查询定义如下:

( ) { ( ) ( )}
NL-TSQ MP Q = MP j | ∀MP i ∈ MP, Traj-StrSim MP j , MP Q ⩾ Traj-StrSim MP i , MP Q (23)
其中, MP Q 是轨迹相似性查询的查询键, Traj-StrSim(MP j , MP Q ), Traj-StrSim(MP i , MP Q ) 是定义 14 中轨迹相似性的
计算, 根据计算得到与查询键 MP Q 轨迹相似性程度最高的 MP j , MP j 所组成的轨迹为相似轨迹查询结果.

6 实 验

为了评估所提出 NUGC_LI 索引的查询性能和动态更新效率, 使用 C++编译语言在 Ubuntu 20.04 环境下进行
代码实现, 并将结果与 B+树和经典学习索引 RMI 进行对比, 实验硬件环境为: Intel(R) Core(TM) i7-5600U CPU @
2.60 GHz, RAM 16.0 GB, Linux 5.15.0-76-generic.
6.1 实验设置
实验数据集包括真实采集的出租车移动轨迹、系统模拟仿真的火车移动轨迹与随机生成的移动轨迹这 3 类,
通过对不同类型数据集的测试保证了实验的完整性与结果的准确性. 轨迹数据集基本属性如表 3 所示, 其中真实
采集的出租车移动轨迹为 2013 年 10 月 22 日 0–24 时期间 302 辆出租车的轨迹片段, 涉及移动对象点数量为
917 006 个; 系统模拟仿真的火车移动轨迹为 2003 年 11 月 20 日 6–9 时期间 562 辆火车的轨迹片段, 涉及移动对
象点数量为 51 544 个; 随机生成的是以北京市某地坐标 (116.231 7, 39.542 7) 为期望数组, 维数为 2, 协方差矩阵为
[1, 1.5], [1.5, 4] 的随机函数生成的数据点, 涉及数据点数量为 1 000 000 个. 深圳市数据集密度分布呈现显著的空
间聚集性, 网格最大密度值 47, 对应城市热点区域, 网格密度标准差为 2.4, 占总网格数 22% 的高密度网格 (Dens≥1)
覆盖了 83% 的移动对象点; 柏林市数据集密度沿预设铁路线呈带状分布, 网格最大密度值 8.8, 网格密度标准差为
0.5, 分布相对均匀; 随机数据集服从二维高斯分布, 密度峰值位于期望坐标 (116.231 7, 39.542 7), 密度值随距离衰
减, 网格最大密度值为 3, 网格密度标准差为 1.2, 且约 20% 的网格覆盖了 65% 的数据点. 在本节中所使用的数据
均建立在第 3 节非均匀网格降维的基础上, 分别将上述 3 个数据集进行非均匀网格降维, 然后分别在这 3 个降维
后的一维非均匀网格编码数据集上建立 B+树、RMI、ALEX 和 NUGC_LI 索引结构, 同时在未进行编码的 3 个原
始数据集上建立 3DR 树与 TB 树.