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

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

索引查询时间较 B+树降低 88.1%, 较 RMI 降低 22.64%, 较 ALEX 降低 3.75%, 较 3DR 树降低 65.4%, 较 TB 树降
低 63.48%; 当区域窗口为 50% 时, 较 B+树降低 76.36%, 较 RMI 降低 36.14%, 较 ALEX 降低 13.2%, 较 3DR 树降
低 60.32%, 较 TB 树降低 36.96%; 当区域窗口为 75% 时, 较 B+树降低 63.02%, 较 RMI 降低 36.5%, 较 ALEX 降
低 18.22%, 较 3DR 树降低 50.44%, 较 TB 树降低 26.96%; 当区域窗口为 100% 时, 较 B+树降低 64.31%, 较 RMI
降低 36.56%, 较 ALEX 降低 20.21%, 较 3DR 树降低 53.08%, 较 TB 树降低 52.67%. 可见在不同查询区域窗口下,
NUGC_LI 索引的性能始终优于 B+树、RMI、ALEX、3DR 树和 TB 树索引, 且在随机生成数据集中更为稳定.
6.3.2 最近邻查询
在不同索引结构的 3 种不同数据集上进行最近邻查询实验, 查询时间的实验结果对比如图 15 所示.

0.04

0.6
深圳市及随机数据查询时间 (s) 0.4 0.02 柏林市数据查询时间 (s) 深圳市数据集

柏林市数据集
随机数据集

0.2

0 0
B+树 RMI ALEX NUGC_LI 3DR树 TB树
索引结构
图 15 不同索引最近邻查询时间对比图

在进行最近邻查询时, 会在每一轮由随机函数生成一个随机查询点, 在不同索引结构中查找距离该查询点最
近的邻居点, 共设置 10 轮, 每一轮生成一个随机查询点, 将 10 次最近邻查询的平均时间作为实验结果.
与范围查询一样, 因为柏林市数据集规模较小, 查询时间较另外两个数据集相差两个数量级, 因此图 15 中, 深
圳市和随机数据集的查询时间对应左纵轴刻度, 柏林市数据集的查询时间对应右纵轴刻度. 可以看出, 基于
NUGC_LI 索引的最近邻查询与其他索引结构下的查询相比, 查询时间明显降低. 除 ALEX 索引外, 对于不同数据
集的查询性能提升效果则各有不同, 在柏林市数据集上性能提升最少, 但也比 RMI 提升了 98.81%. 在其他数据集
上, 查询性能提升均达 90% 以上. 相比于 ALEX 索引, 由于柏林市数据集较小, 同时轨迹分布相对均匀, 所以
NUGC_LI 和 ALEX 索引查询性能相当, 随着数据集增大和轨迹分布更加复杂, NUGC_LI 相比于 ALEX 索引在深
圳市数据集和随机数据集上分别提升 71.76% 和 30%.
为了使得基于 NUGC_LI 的最近邻查询更符合实际应用场景的需求, 在最近邻查询的基础上, 拓展查询方式
为 k 近邻查询, 即在不同索引结构中查找距离查询点最近的 k 个邻居点, 通过新建一个可容纳 k 个元素的最大堆
实现. 选择了深圳市真实出租车数据集和随机生成数据集, 取 k 的值分别为 1、5、10 和 15, 并开展实验. 实验的
查询时间结果如图 16 所示.
因为基于 ALEX 和 NUGC_LI 索引的 k 近邻查询时间比其他两种索引小两个数量级, 为便于展示, B+树、
RMI、3DR 树与 TB 树索引的查询时间刻度为左纵轴, ALEX 和 NUGC_LI 索引查询时间刻度为右纵轴. 通过查询
时间比较分析可知, 在深圳市数据集中, 随着 k 值的增长, NUGC_LI 索引的查询时间较 B+树索引降低至少
99.87%, 较 RMI 索引降低至少 97.56%, 较 ALEX 索引降低至少 38.13%, 较 3DR 树索引降低至少 99.09%, 较 TB
树索引降低至少 96.17%, 但降低幅度均呈现逐渐下降趋势. 在随机生成数据集中, 随着 k 值的增长, NUGC_LI 索
引的查询时间较 B+树索引降低至少 99.84%, 较 RMI 索引降低至少 98.16%, 较 ALEX 索引降低至少 4.96%, 较