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

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

{ }
RMP = mp ,mp ,...,mp ′ (5)
′
′
1 2 n
⟨( ) ( ) ( )⟩
′
mp = t 1 ,Loc , t 2 ,Loc ,..., t n ,Loc ′ n (6)
′
′
1
2
其中, mp 由降维后的移动对象位置点与时间组成二元组, 按照时间顺序排列而成.
′
2.2 数据查询相关定义
定义 4. 空间范围查询 RangeMO.
给定一个空间查询矩形框 Bbox, 返回经过该区域的移动对象, 空间范围查询 RangeMO 定义为:

′ ′ ′
RangeMO(Bbox, MP) = {MP | MP ⊆ MP, ∀mp ∈ MP , ∃Loc ∈ mp∧ Loc ∈ Bbox} (7)
定义 5. 最近邻查询 NNMO.
非均匀网格降维算法可以使相邻单元格可以被快速定位, 具体说明可见第 5.2 节, 所以基于学习索引的最近
邻查询问题被简化为了多个点查询, 定义如下:

( ) { ( ) ( ) ( ) ( )}
NNMO P Q , MP = P j | P j ∈ Query P Q-neighbor , ∀P i ∈ Query P Q-neighbor , dis P j ,P Q ⩽ dis P i ,P Q (8)
其中, P Q 是最近邻查询的查询键, P Q-neighbo 是对查询键所在单元格相邻一圈网格的点查询操作, 该函数首先定位
r
查询键的 P Q 位置, 并获取该网格内存储的移动对象点数组, 依次遍历并计算得到最近邻居, 若该区域只有一个网
格, 则在网格中寻找最接近该数据点的邻居点; 否则对其所在网格外围一周网格内的数据点进行遍历计算, 以查找
最近邻居.
定义 6. Loc-MP 轨迹相似性度量.
移动对象是一组按照时间顺序排列而成的位置点, 通过离散采样表示对象点连续移动的趋势. 为了在多维空
间中较为方便地比较不同轨迹的相似程度, 定义了一种 Loc-MP 轨迹相似性度量方式.
给定移动对象位置点 Loc, 移动对象 MP, 则 Loc-MP 轨迹相似性为:

Sim(Loc, MP) = max (dis(Loc,P i )) (9)
P i ∈MP
其中, dis(Loc,P i ) 为移动对象位置点 Loc 与移动对象 MP 中第 i 个位置点的欧氏距离, 由此可知将给定点 Loc 与给
定移动对象点 P i ∈ MP 的最大欧氏距离值定义为 Loc-MP 轨迹相似性.
定义 7. MP-MP 轨迹相似性度量.
考虑到对于不同的轨迹而言, 采样的频率和起始终止时间并不总是完全一致, 所以任意两条轨迹间的相似性
度量需要分别选取轨迹代表点, 以代表点的相似程度来衡量轨迹的相似程度. 代表点的选择可以基于多种策略, 如
等间隔采样、基于特征的采样、基于聚类的采样等, 根据轨迹的不同特性进行相应选择, 为确保查询效率, 选取等
间隔采样的方式, 在固定时间间隔内选取位置点平均值作为代表点.
给定两条起始终止时间相同的移动对象片段 MP 1 和 MP 2 , 通过等间隔采样与均值计算分别得到 n 个代表点,
MP 1 和 MP 2 两条轨迹之间的相似性为:

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

Traj-Sim(MP 1 , MP 2 ) = e −MP-Sim(MP 1 ,MP 2 ) (11)
其中, MP-Sim(MP 1 , MP 2 ) 是根据定义 7 计算的轨迹中所有给定点距离另一轨迹的相似性度量, 即两条轨迹间的相
似性度量, Traj-Sim(MP 1 , MP 2 ) 则是对轨迹间的相似性度量值进行归一化处理, 从公式 (11) 易知 Traj-Sim(MP 1 , MP 2 ) ∈
(0,1], 且值越大, 轨迹相似性程度越高.
定义 8. 轨迹相似性查询 Traj-SQ.
轨迹相似性查询为给定轨迹 MP Q 计算其与其他所有轨迹的相似性程度, 并返回相似性程度最高的轨迹 MP j ,
定义如下:

( ) { ( ) ( )}
Traj-SQ MP Q = MP j | ∀MP i ∈ MP, Traj-Sim MP j , MP Q ⩾ Traj-Sim MP i , MP Q (12)