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

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

点的相似程度来衡量轨迹的相似程度, 采用等间隔取样的方式, 分别对数据集以 1、5、10、15、30 min 这 5 种时
间区间进行轨迹划分. 最终如图 18 所示, 通过综合性能对比, 选定 15 min 为子轨迹划分时间阈值. 在不同索引结
构的 3 种不同数据集上进行相似轨迹查询实验, 查询时间的实验结果对比如图 19 所示.

350 85
316.171 4 降维时间代价
300
82.5 空间位置关系相似度 80
降维时间代价 (s) 200 72.54 71.38 68.9 75 空间位置关系相似度 (%)
250
150
70
106.68
100
39.42
50
19.43
5.87 64 61.58 65
0 1.75 60
未划分 1 5 10 15 30
时间区间 (min)
图 18 不同时间区间对性能的影响

1 600
5 000
1 400
深圳市及随机数据查询时间 (s) 3 000 1 000 柏林市数据查询时间 (s) 深圳市数据集
4 000
1 200

800
柏林市数据集
2 000
600
随机数据集
400
1 000
200
0 0
B+树 RMI ALEX NUGC_LI 3DR树 TB树
索引结构
图 19 不同索引相似轨迹查询时间对比图

与上述查询实验一样, 因为柏林市数据集规模较小, 查询时间较另外两个数据集相差较大, 因此图 18 中, 深圳
市和随机数据集的查询时间对应左纵轴刻度, 柏林市数据集的查询时间对应右纵轴刻度. 通过查询时间对比, 可知
基于 NUGC_LI 索引的相似轨迹查询与其他索引结构下的查询相比均具有优势, 在随机数据集上性能提升最少,
仅比 ALEX 提升 3.77%, 比 RMI 提升了 25.24%, 比 TB 树提升 67.47%, 比 3DR 树提升 67.58%, 比 B+树提升
70.5%, 在深圳市和柏林市数据集上, 均比 ALEX 提升 10% 以上, 比 RMI 提升 30% 以上, 比 3DR 树和 TB 树提升
69% 以上, 比 B+树提升 73% 以上.
此外, 将基于 NUGC_LI 的相似轨迹查询拓展为 k 条相似轨迹查询, 即在不同索引结构中查找与查询轨迹最
相似的 k 条轨迹, 通过新建一个可容纳 k 个元素的最大堆实现. 选择了深圳市真实出租车数据集和随机生成数据
集, 取 k 的值分别为 1、3、5 和 7, 并开展实验. 实验的查询时间结果如图 20 所示.
因为基于 RMI 与 NUGC_LI 索引的相似轨迹查询时间比 B+树、3DR 树和 TB 树索引降低较为明显, 为便于
展示, B+树、3DR 树和 TB 树索引的查询时间刻度为左纵轴, RMI、ALEX 与 NUGC_LI 索引查询时间刻度为右
纵轴. 通过查询时间比较分析可知, 在深圳市数据集中, 随着 k 值的增长, NUGC_LI 索引的查询时间较 B+树索引
降低至少 82.85%, 较 RMI 索引降低至少 33.42%, 较 3DR 树索引降低至少 75.41%, 较 TB 树索引降低至少 75.65%,
且降低幅度较为稳定, 随 k 值影响变化不大. 在随机生成数据集中, 随着 k 值的增长, NUGC_LI 索引的查询时间