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

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

尤其是 NUGC_LI 索引的更新时间较其他索引减少了 3 个数量级, 优势明显. 综合比较下, B+树索引在更新时所耗
费的时间最多, 其次分别是 RMI、ALEX、3DR 树和 TB 树. RMI 需要重建, ALEX 在非均匀轨迹数据上性能下降,
反而传统移动对象在部分非均匀的数据上更新效果更好. NUGC_LI 所花费的更新时间比其他索引减少了至少
93.76%. 此外, 以数据量最大的随机数据集为例, 采用逐步增加数据规模的方法, 分别以 25%、50%、75% 和
100% 的比例进行伸缩性测试. 如后文图 12 所示, 在不同数据比例下, NUGC_LI 索引的性能始终优于 B+树、RMI、
ALEX、3DR 树以及 TB 树索引, 且随着数据量的逐渐增大, 更新时间不会产生较大的抖动, 所以 NUGC_LI 可以
很好地扩展到更大的数据集.

B+树 RMI ALEX
2.0 NUGC_LI 3DR树 TB树 70
B+树、RMI、ALEX、NUGC_LI 索引构建时间 (s) 1.0 50 3DR树、TB树索引构建时间 (s)
60
1.5
40
30
20
0.5

0 10
0
25 50 75 100
数据规模 (%)
图 10 可变数据量比例下不同索引构建时间伸缩性对比图

×10 −3
0.30 ×10 −3 140
索引更新时间 (s) 0.5 索引更新时间 (s) 0.20 索引更新时间 (s) 0.10 索引更新时间 (s) 100
0.14
120
0.25
1.0
0.12
80
0.15
0.08
60
0.06
0.10
40
0.04
0 0.05 0 0.02 0 20 0
深圳市 柏林市 随机数据 深圳市 柏林市 随机数据 深圳市 柏林市 随机数据 深圳市 柏林市随机数据
数据集名称 数据集名称 数据集名称 数据集名称
(a) B+树索引 (b) RMI索引 (c) NUGC_LI索引 (d) ALEX索引
与B+树比较 与ALEX比较 与3DR树比较
×10 −3 ×10 −3 与TB树比较 与RMI比较
60 100
索引更新时间 (s) 60 索引更新时间 (s) 40 NUGC_LI更新时间 提升百分比 (%) 60
100
50
80
80
30
40
40
20
20
0 10 0 20 0
深圳市 柏林市 随机数据 深圳市 柏林市 随机数据 深圳市 柏林市 随机数据
数据集名称 数据集名称 数据集名称
(e) 3DR树索引 (f) TB树索引 (g) NUGC_LI与其他索引对比
图 11 不同索引更新时间对比图

6.3 查询实验
6.3.1 范围查询
对不同索引结构的数据集进行范围查询, 查询时间结果如图 13 所示. 在进行范围查询时, 通过随机函数生成
(X min ,Y min ), 设置固定范围长度
随机查询点, 然后以该点为区域最小点 10, 故查询区域为 (X min ,X min +10,Y min ,Y min +10),
查询轮数为 5 轮, 在每一轮中随机生成查询点, 取 5 轮查询时间的平均值作为实验结果.