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

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

出了用于大型时序数据库上评估 k 近邻查询的并行解决方案, 根据查询质量和时间性能的各种度量对其进行比
较, 并提供了使用应用程序数据特征来确定为该应用程序选择哪种算法及参数的工具, 并在 Spark 上实现, 在节点
集群上进行了评估实验.
1.3.3 相似轨迹查询
根据查询轨迹特征, 在对轨迹进行降维之后, 使用标记特征的索引方法, 查询符合相似度定义的轨迹数据. 相
似轨迹查询包含基于阈值的查询, 即给定一个相似值, 求解轨迹数据集中所有与查询对象的相似值小于阈值的轨
迹. 还包括 Top-k 相似性查询, 即对基于阈值的相似性查询结果进行排序并进行筛选. 因为相似轨迹查询所用实验
数据集较为庞大, 查询代价较高, 现有轨迹相似性查询算法主要基于分布式集群环境. 2006 年, Frentzos 等人 [58] 通
过定义相似度的度量方法解决移动对象相似性搜索的问题, 提出了近似方法降低其计算成本, 并开发了新的度量
和启发式方法来支持移动对象数据库中的 k 相似轨迹搜索. 2017 年, Xie 等人 [59] 提出分布式查询框架, 用于处理大
量移动对象数据上的轨迹相似性搜索, 在分布式数据处理引擎 Spark 中实现该框架, 支持豪斯多夫距离和弗雷歇
距离查询. 此外, 还有连续查询、并行查询、最短路径查询等各类查询, 不同的应用场景和用户需求催生了不同的
查询方法.

2 问题定义

基于非均匀网格降维构建学习索引, 为验证查询性能, 引入了 3 种查询方法: 范围查询、最近邻查询与相似轨
迹查询, 本节将对数据降维、学习索引及查询算法的相关定义进行说明. 本节定义涉及符号说明如表 1 所示.

表 1 缩略符号定义表

符号 说明 符号 说明
MP 移动对象 Loc 移动对象位置点
t 时间 x 经度
y 纬度 f 位置降维函数
RMP 降维轨迹数据 RangeMO 范围查询
Bbox 矩形边界框 NUGC 非均匀网格降维算法
CDF 累积分布函数 P i 移动对象查询点
NNMO 最近邻查询 Loc-MP 轨迹相似性度量
MP-MP 轨迹相似性度量 Traj-Sim 轨迹间的相似性度量
MP-Sim 轨迹点距离另一轨迹的相似性度量 Traj-SQ 轨迹相似性查询

2.1 数据降维基础定义
定义 1. 移动对象 MP.
一个移动对象由一组移动对象位置点和时间组成, 在数据库系统中用数据类型 MP 来表示:

MP = {mp 1 ,mp 2 ,...,mp n } (1)

mp = ⟨(t 1 ,Loc 1 ),(t 2 ,Loc 2 ),...,(t n ,Loc n )⟩ (2)

Loc = {(x,y) | x,y ∈ R} (3)
其中, Loc 为移动对象位置点, x 为经度, y 为纬度, t 为时间, 移动对象位置点按照时间顺序排列.
定义 2. 位置降维函数 f.

f : Loc → Loc ′ (4)
利用非均匀网格降维算法, 针对数据分布情况, 通过网格密度计算数据密集程度, 并根据网格密度采取平衡措
施, 将移动对象位置点 Loc 映射为一维编码后得到对象 Loc . 非均匀网格降维算法具体内容详见第 3 节.
′
定义 3. 降维轨迹数据 RMP.
经降维函数 f 作用后得到: