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

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

对不同节点阈值下索引的构建时间和查询时间进行统计分析, 并对这两者取相同权重进行加权计算得到综合
时间代价, 即图 8 折线数据点所示, 通过折线图趋势, 发现当 X 取 80% 时, 索引节点的综合时间代价是 0.85 s 为最
优值, 故取该值为节点阈值的实验参数.
6.2.2 索引构建时间对比
对深圳市、柏林市和随机数据集分别构建了 B+树、RMI、ALEX、NUGC_LI、3DR 树和 TB 树索引, 构建
时间结果如图 9 所示. 因为在深圳市数据集和随机数据集中, 基于 3DR 树和 TB 树索引构建时间比其他索引大两
个数量级, 为便于展示, B+树、RMI、ALEX 与 NUGC_LI 索引的构建时间刻度为左纵轴, 3DR 树和 TB 树索引构
建时间刻度为右纵轴. 在真实轨迹、仿真轨迹和随机数据集上, 6 种索引的构建时间呈现出同一趋势, TB 树索引
耗费时间最多, 其次分别是 3DR 树、B+树、RMI 和 ALEX. NUGC_LI 所用时间最少, 比 TB 树降低至少 91.45%,
比 3DR 树降低至少 89.63%, 比 B+树降低至少 90.38%, 比 RMI 降低至少 87.46%, 比 ALEX 降低至少 13.71%. 此
外, 以数据量最大的随机数据集为例, 采用逐步增加数据规模的方法, 分别以 25%、50%、75% 和 100% 的比例进
行伸缩性测试. 如后文图 10 所示, 在不同数据比例下, NUGC_LI 索引的性能始终优于 B+树、RMI、ALEX、
3DR 树以及 TB 树索引, 且随着数据量的逐渐增大, 构建时间不会产生较大的抖动, 所以 NUGC_LI 可以很好地扩
展到更大的数据集.

60 0.10
1.6 50 0.08
B+树、RMI、ALEX、NUGC_LI 索引建立时间 (s) 1.0 40 3DR树、TB树索引建立时间 (s) 索引建立时间 (s) 0.06
1.4
1.2

30
0.8
0.04
0.6
20
0.4
0.2
0
0 10 0.02 0
B+树 RMI ALEX NUGC_LI 3DR树 TB树 B+树 RMI ALEX NUGC_LI 3DR树 TB树
索引结构 索引结构
(a) 深圳市数据集 (b) 柏林市数据集
与B+树比较 与ALEX比较 与3DR树比较
与TB树比较 与RMI比较
1.8 60 100
B+树、RMI、ALEX、NUGC_LI 索引建立时间 (s) 1.2 40 3DR树、TB树索引建立时间 (s) NUGC_LI构建时间提升百分比 (%) 80
1.6
1.4

1.0
60
0.8
40
0.6
20
0.4
0.2
0 0 20 0
B+树 RMI ALEX NUGC_LI 3DR树 TB树 深圳市 柏林市 随机数据
索引结构 数据集名称
(c) 随机数据集 (d) NUGC_LI与其他索引对比
图 9 B+树、RMI、ALEX、NUGC_LI 不同索引建立时间对比图

6.2.3 索引更新时间对比
此外, 对不同数据集在 6 种索引上的更新操作进行了对比实验, 索引更新时间的实验结果如图 11 所示. 在
B+树、RMI、ALEX、NUGC_LI、3DR 树和 TB 树 6 种不同的索引结构上, 这 3 个数据集的更新时间有所不同,