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

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

B+树 RMI ALEX ×10 10 −5 1.2 深圳市数据集 柏林市数据集 随机数据集
B+树、RMI、ALEX、3DR树、TB树 索引更新时间 (s) 0.5 5 NUGC_LI索引更新时间 (s) 深圳市及随机数据查询时间 (s) 1.0 0.04 柏林市数据查询时间 (s)
TB树
3DR树
NUGC_LI
1.0
0.8
0.6
0.02
0.4

0
25 50 75 100 0 0.2 0 B+树 RMI ALEX NUGC_LI 3DR树 TB树 0
数据规模 (%) 索引结构
图 12 可变数据量比例下不同索引更新时间伸缩性对 图 13 不同索引范围查询时间对比图
比图

因为柏林市数据集规模较小, 查询时间较另外两个数据集相差两个数量级, 因此在图 13 中, 深圳市和随机数
据集的查询时间对应左纵轴刻度, 柏林市数据集的查询时间对应右纵轴刻度. 通过查询时间对比, 易知基于
NUGC_LI 索引的范围查询具有明显优势, 除 3DR 树和 TB 树外, 在柏林市数据集上性能提升最少, 仅比 ALEX 提
升 8.74%, 比 RMI 提升 29.38%, 比 B+树提升 52.72%. 除 3DR 树和 TB 树外, 在随机数据集上性能提升最高, 比
ALEX 提升 20.21%, 比 RMI 提升 39%, 比 B+树提升 70.73%. NUGC_LI 索引相比于 3DR 树和 TB 树索引在 3 个
数据集上的提升相对稳定, 提升均在 50% 左右.
为了进一步研究基于 NUGC_LI 的范围查询在不同区域窗口下的性能区别, 选择了深圳市真实出租车数据集
和随机生成数据集, 对这两个数据集分别进行划分, 各生成 4 种不同大小的区域窗口进行查询. 查询时间结果如
图 14 所示.

B+树 RMI ALEX B+树 RMI ALEX
1.4 NUGC_LI 3DR树 TB树 1.4 NUGC_LI 3DR树 TB树
1.2 1.2
1.0 1.0
查询时间 (s) 0.8 查询时间 (s) 0.8

0.6
0.6
0.4 0.4
0.2 0.2

0 0
25 50 75 100 25 50 75 100
区域窗口比例 (%) 区域窗口比例 (%)
(a) 深圳市数据集 (b) 随机数据集
图 14 不同区域窗口查询时间对比图

通过查询时间比较分析可知, 在深圳市数据集中, 当区域窗口为 25% 时, NUGC_LI 索引查询时间较 B+树降
低 87.75%, 较 RMI 降低 5.55%, 较 ALEX 降低 20.37%, 较 3DR 树降低 61.3%, 较 TB 树降低 57.76%; 当区域窗口
为 50% 时, 较 B+树降低 74.27%, 较 RMI 降低 35.63%, 较 ALEX 降低 21.3%, 较 3DR 树降低 49.85%, 较 TB 树降
低 45.92%; 当区域窗口为 75% 时, 较 B+树降低 62.82%, 较 RMI 降低 39.5%, 较 ALEX 降低 7.87%, 较 3DR 树降
低 35.96%, 较 TB 树降低 32.83%; 当区域窗口为 100% 时, 较 B+树降低 64.53%, 较 RMI 降低 37.47%, 较 ALEX 降
低 11.15%, 较 3DR 树降低 56.14%, 较 TB 树降低 55.28%. 在随机生成数据集中, 当区域窗口为 25% 时, NUGC_LI