Approximate Geometric Query Structures:Maximum-Spread k-d Trees

Maximum-Spread k-d Trees

One very popular class of BSP tree is the k-d tree, see Chapter 16. Although there are very few theoretical bounds known on these structures, there is a lot of empirical evidence that shows them to be extremely efficient for numerous geometric applications. In particular, one variant the maximum-spread k-d tree has long been considered an ideal k-d tree. Given a set of points S and a particular axis dimension xd, define the spread of S in xd to be the difference between the minimum and maximum coordinates of the points in that dimension. The maximum-spread k-d tree is formed by choosing at each internal node a cutting plane orthogonal to the axis of maximum spread placed at the median point in this direction, see for example [16]. Arya et al. [1] applied the maximum-spread k-d tree to their approximate nearest-neighbor searching algorithm and experimentally showed that they were comparable to the theoretically efficient BBD tree. Later Dickerson et al. [9, 11] proved the following theorem regarding maximum-spread k-d trees, referred to there as longest-side k-d trees:

THEOREM 26.8 Suppose we are given a maximum-spread k-d tree T constructed on a set S of n points in IRd. Then the packing function ρ(n) of T for a region annulus A is O(logd1 n). That is, the class of maximum-spread k-d trees is an O(logd1 n)-quasi-BAR tree.

Although the bound is not as good as for BBD trees and BAR trees, the simplicity of the structure yields low constant factors and explains why in practice these trees perform so well. Experimental comparisons to BBD trees and BAR trees verified this result and showed that only for very highly clustered data did the dependency on logd1 n become prominent [1, 11].

In practice, unless data is highly clustered and the dimension is moderately large, the maximal-spread k-d tree is an ideal structure to use. However, for such data sets both the BBD tree and the BAR tree revert to the same behavior as the maximal-spread tree, and they perform well even with highly clustered data. Because of its simpler structure, the BBD tree is potentially more practical than the BAR tree.

Related posts:

Leave a comment

Your email address will not be published. Required fields are marked *