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

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

3DR 树索引降低至少 96.23%, 较 TB 树索引降低至少 94.68%. 可见在进行 k 近邻查询时, 无论 k 取何值, 除 ALEX
索引外, NUGC_LI 索引都具有明显优势, 且在不同数据集中查询性能都十分稳定. 相比于 ALEX 索引, NUGC_LI
在 k 为 1 时优势明显, 在深圳市数据集和随机数据集上分别降低 71.76% 和 30%, 然而随着 k 值增加, 优势逐渐下
降, 但最终仍优于 ALEX 索引.

B+树 RMI 3DR树 B+树 RMI 3DR树

1.4 TB树 ALEX NUGC_LI 0.020 0.8 TB树 ALEX NUGC_LI 0.025
1.2
B+树、RMI、3DR树、TB树 索引查询时间 (s) 1.0 0.010 ALEX、NUGC_LI索引查询时间 (s) B+树、RMI、3DR树、TB树 索引查询时间 (s) 0.4 0.015 ALEX、NUGC_LI索引查询时间 (s)
0.020
0.6
0.015
0.8
0.6
0.010
0.4
0.2
0.005
0.2
0 0 0 0.005
0
1 5 10 15 1 5 10 15
最近邻居点个数 最近邻居点个数
(a) 深圳市数据集 (b) 随机数据集
图 16 不同 k 值的最近邻查询时间对比图

此外, 考虑到移动对象数据还具有分布不均匀的特点, 还随机抽取了深圳市数据集中, 不同密度网格中的点作
为查询点进行最近邻查询, 研究网格密度对于最近邻查询性能的影响. 图 17 是对网格密度处于 0<Dens Q1 <0.5、
0.5<Dens Q2 <1、1<Dens Q3 <5、Dens Q4 >5 这 4 个区间的查询点进行实验后得到的结果.

B+树 RMI ALEX

3DR树 TB树 NUGC_LI 0.000 3
B+树、RMI、ALEX、3DR树、TB树 索引查询时间 (s) 0.6 0.000 2 NUGC_LI索引查询时间 (s)
0.8

0.4
0.000 1
0.2

0 0
(0,0.5) (0.5,1) (1,5) (5,+∞)
查询点所在网格密度
图 17 不同网格密度的最近邻查询时间对比图

同样因为基于 NUGC_LI 索引的最近邻查询时间比其他两种索引小 3 个数量级, 为便于展示, B+树、RMI、
ALEX、3DR 树和 TB 树索引的查询时间刻度为左纵轴, NUGC_LI 索引查询时间刻度为右纵轴. 通过查询时间比
较分析可知, 在不同网格密度的最近邻查询中, NUGC_LI 索引的性能始终优于其他索引, 至少可比 B+树提升
99.96%, 比 RMI 提升 99.07%, 比 ALEX 提升 98.55%, 比 3DR 树提升 99.93%, 比 TB 树提升 99.92%, 但随着网格密
度的升高, NUGC_LI 的查询优势逐渐减小.
6.3.3 相似轨迹查询
每条移动对象轨迹都包含特定时间段内的所有行程, 为了取不同轨迹在同一时间段内的代表点, 从而以代表