стр. 93 |

possibility is to use kd-trees. The name initiated from work in a k-dimensional space,

hence, in our setting these trees should be called dd-trees. But we will keep the commonly

used name.

The kd-tree data structure is based on a recursive subdivision of space into disjoint

rectangular regions called boxes. Each node of the tree is associated with such a box B

and with a set of data points that are contained in this box. The root node of the tree is

associated with the bounding box that contains all the data points. Consider an arbitrary

node in the tree. As long as the number of data points associated with this node is greater

than a small quantity, called the bucket size, the box is split into two boxes by an axis-

orthogonal hyperplane that intersects this box. There are a number of different splitting

rules, which determine how this hyperplane might be selected. We will discuss them in

detail later on. The two resulting boxes are the cells associated with the two children of

this node. The data points lying in the original box are split between these two children,

depending on which side of the splitting hyperplane they are. Points lying on the hyperplane

itself may be associated with either child (according to the dictates of the splitting rule).

When the number of points associated with the current box falls below the bucket size then

the resulting node is declared a leaf, and these points are stored with the node.

Thus, in addition to the data points themselves, a kd-tree is speciп¬Ѓed by two additional

parameters, the bucket size and a splitting rule. The tree itself is a binary tree with two

238 Data structures

different types of nodes, splitting nodes and leaves. The root node, is in principle a splitting

node (unless the number of points is less than the bucket size), which contains additional

information such as the number of points, the space dimension, and the bucket size. A

splitting node stores the integer splitting dimension indicating the coordinate axis orthogonal

to the cutting hyperplane. It also stores the splitting value where the hyperplane intersects

the axis of the splitting dimension. Moreover, it contains two pointers, one for each child

(corresponding to the low and high sides of the cutting plane). A leaf node stores the number

of points that are associated with this node and an array of the indices of the points lying in

the associated box.

Next, let us discuss possible splitting rules. To this end we denote by Y the current subset

of data points in the current box B. Let B(Y ) вЉ† B be the bounding box of Y . For the root

node, Y is equal to X , the set of all points, and B = B(X ) is the bounding box of the

centers. The aspect ratio of a box is the ratio of its longest and shortest side lengths. Given a

dimension, the point spread of Y along this dimension is the difference between the largest

and the smallest coordinate of all points in Y for this dimension. Finally, for a set A of n

numbers, the median is the number m that partitions A into two subsets, one with n/2

elements that are not greater than m and the other with n/2 elements that are not less than

m. Typical splitting rules are as follows.

r Standard kd-tree splitting rule The splitting dimension is the dimension of the maximum spread

of Y . The splitting value is the median of the coordinates of Y along this dimension.

r Cyclic splitting rule This splitting rule works in the same way as the standard rule, but the splitting

dimension is not chosen by the maximum spread. Instead all coordinates are chosen one after the

other in a cyclic way.

r Midpoint splitting rule The splitting dimension is the dimension of the longest side of B. The

splitting value is the midpoint of this side of the box. If there is more than one dimension with the

longest side choose the dimension with the widest point spread.

r Sliding midpoint rule The splitting dimension and splitting value are chosen as in the case of the

midpoint splitting rule, provided that points from Y lie on both sides of the cutting plane. If this

is not the case then the cutting plane is moved from the empty side towards the п¬Ѓrst point of Y .

The coordinate along the splitting dimension of this point now determines the splitting value. The

point itself is put into the former empty (child-)box while all other points from Y remain in the

other box.

Obviously, several other splitting rules are possible, but those mentioned above are com-

monly used. Before we analyze the complexity of building a kd-tree using the standard

splitting rule, we want to point out that on the one hand this rule may lead to boxes with

arbitrarily high aspect ratios. On the other hand, the midpoint splitting rule produces boxes

with bounded aspect ratios but it may lead to trivial splits. These are splits where one of

the child boxes does not contain a point at all. Hence the depth and size of a tree can be

arbitrarily large, even exceeding O(N ). A possible way out is the sliding midpoint rule. It

cannot produce trivial splits and therefore both depth and size are bounded by O(N ). It may

also produce boxes of high aspect ratio but this seems to be less likely. A more thorough

analysis of the complexity will follow. Figure 14.4 shows a decomposition of space using

14.2 kd-Trees 239

Fig. 14.4 A kd-tree decomposition with standard splitting rule (on the left) and sliding midpoint

splitting rule (on the right).

the standard splitting rule (on the left) and the sliding midpoint rule (on the right). In both

cases the bucket size has been chosen as one.

Assuming that the splitting rule is chosen, that the bounding box B B of X is at hand, and

that b denotes the bucket size, Algorithm 4 describes the procedure of building a kd-tree.

Algorithm 4 Build kd-tree

Data points X = {x1 , . . . , x N } вЉ† Rd , box B.

Input:

Output: Root of a kd-tree.

if X contains at most b points then

Return a leaf storing the indices of these points.

else

Determine splitting dimension and value and split the current bounding box B and its

points into two subboxes B1 , B2 and two subsets of points Y1 , Y2 , respectively.

Apply this algorithm to Y1 , B1 , resulting in a pointer ОЅ1 .

Apply this algorithm to Y2 , B2 , resulting in a pointer ОЅ2 .

Create a splitting node ОЅ storing the splitting dimension, the splitting value, the left

child ОЅ1 , and the right child ОЅ2 .

Return ОЅ.

Let us analyze this algorithm when the standard splitting rule is employed. The most

expensive step in each recursive call is to п¬Ѓnd the splitting value. Median п¬Ѓnding can be

done in linear time but the necessary algorithms are rather complicated. It appears to be

easier to presort the set of points on each coordinate in a preprocessing step, which can be

done in O(d N log N ) time and needs additional O(d N ) space at least temporarily to keep

the sorted lists. Then it is easy to п¬Ѓnd the median in linear time. It is also easy to construct

240 Data structures

the two sorted lists for the recursive calls from the given list in linear time. Hence, the time

T (N ) needed to build the tree satisп¬Ѓes

O(1) if N в‰¤ b,

T (N ) =

O(N ) + 2T ( N /2 ) if N > b

which on solving the equation turns out to be O(N log N ). Finally, because a kd-tree is a

binary tree with O(N ) leaves and because every internal node uses O(1) space the total

amount of space is O(N ). Thus we have proven

Theorem 14.6 To construct the kd-tree for N points in Rd using the standard splitting

rule, Algorithm 4 needs O(d N log N ) time and O(d N ) space.

A consequence of this result is that a kd-tree built with the standard splitting rule has

O(log N ) depth. As pointed out earlier, the other splitting rules do not guarantee this feature.

Nonetheless, if the points are quasi-uniformly distributed then all splitting rules have roughly

the same complexity and need the same space.

Algorithm 5 Range query

Query region R вЉ† Rd and root ОЅ of kd-tree.

Input:

Output: All points contained in R.

if ОЅ is a leaf then

Report all points stored at ОЅ that are in R.

else

Let ОЅ1 and ОЅ2 denote the left and right child of ОЅ, respectively and let B1 and B2 denote

their associated boxes.

for i = 1, 2 do

if Bi is fully contained in R then

Report all points in the tree rooted at ОЅi .

else

if R intersects Bi then

Apply this algorithm to R and ОЅi .

Let us now turn to the range query problem. A possible solution is described in

Algorithm 5. The main test in this algorithm is whether R intersects the box B(ОЅ) as-

sociated with a node ОЅ. If this is rather complicated then it is better to replace R by its

bounding box, to apply Algorithm 5 to the bounding box, and to test the reported points

again in a п¬Ѓnal step.

14.2 kd-Trees 241

стр. 93 |