查询区域可能包含树中所有的点,这种情况下,drain方法将会遍历所有的点,性能将会是不能接受的O(n)。但是,当范围查询算法检测到查询的范围不和kd树的某个节点表示的范围相交的话,那么将会剪除对子树的查找。节省的开销取决于维度和输入数据的一些特性。有研究(Preparata和Shamos,1985)表明范围查询算法的性能是O(n1-1/d+r),r是结果集中点的数目。随着维度的增加,性能逐渐下降。图9-25是一个O(n1-1/d)算法的期望性能,该图表明在小维度下,算法的性能逐渐逼近O(n)。因为还需要考虑r,所以实际性能将会偏离图9-25的理想曲线。
图 9-25 O(n1-1/d)算法的期望性能我们很难生成测试范围查询算法性能的数据。我们只能通过和穷举算法进行比较来证明此算法的效率。下面这些情况下,我们使用n个d维点作为输入来进行比较。这些点的坐标值区间是[0,4096]。
情况1:查询区域包含树中所有的点
我们构建了一个包含kd树中所有点的查询区域。这个例子告诉我们的区间查询算法能够提供的最大性能改进,这种情况下,其性能和kd树的维度d无关。我们会执行大约5~7次实验,然后能看到kd树相关的操作所需要的开销。在表9-7中,穷举算法的开销随着维度d的增加而增大,因为计算d维点之间距离的操作是O(d)而不是常数。穷举算法在高维度上性能轻易地超过了基于kd树的最邻近点算法。
情况2:微小区域
因为结果集中的点数r能较大程度地影响算法的性能,我们构建一系列的场景,使得在维度增加的情况下,r并不改变。由于输入集合的一致性,我们不可能简单地构造一个查询区域。如果我们这样做,那么选择的输入集合总数将会是(1/2)d,也就是说,维度d的增加会导致r的增加。实际上,我们会构建一些查询区域,这些区域的规模随着维度的增加而增加。例如,二维的查询区域会返回0.23*n个点。但是,在三维上,查询区域应该扩展更大的范围。这样的话,我们就能预先限定因子k,结果集包含k*n个点。我们也会比较kd树的实现和穷举方法的实现,n的范围从4096~131 072,d从2~15,结果如图9-26所示。左边的表是kd树实现的典型行为,右边是穷举算法的线性行为。k=0.23时,kd树的实现只是在d=2和n≤8192时表现较好。
图 9-26 第二种情况下,范围查询算法和穷举算法的比较情况3:空区域
我们这样来构造一个查询区域,这个区域就是输入中的一个点。性能见表9-8。kd树能够在很短的时间内就计算完成。我们记录的时间都不到1毫秒。