Algorithms in a Nutshell 2E (2015)
Chapter 10. Spatial Tree Structures
The algorithms in this chapter are concerned primarily with modeling twodimensional structures over the Cartesian plane to conduct powerful search queries that go beyond simple membership, as covered in Chapter 5. These algorithms include:
Nearest Neighbor
Given a set of twodimensional points, P, determine which point is closest to a target query point, x. This can be solved in O(log n) instead of the O(n) brute force solution.
Range Queries
Given a set of twodimensional points, P, determine which points are contained within a given rectangular region. This can be solved in O(n^{0.5}+r) where r is the number of reported points, instead of an O(n) brute force solution.
Intersection Queries
Given a set of twodimensional rectangles, R, determine which rectangles intersect a target rectangular region. This can be solved in O(log_{m} n) where r is the number of reported intersections, instead of an O(n) brute force solution.
Collision Detection
Given a set of twodimensional points, P, determine the intersections between squares of side s centered on these points. This can be solved in O(n log n) instead of an O(n^{2}) brute force solution.
The structures and algorithms naturally extend to multiple dimensions, but this chapter will typically remain limited to twodimensional structures for convenience. The chapter is named after numerous successful attempts to partition ndimensional data using the intuition at the heart of binary search trees.
Nearest Neighbor queries
Given a set of points, P, in a twodimensional plane, you might need to determine the point in P that is closest to a query point x using Euclidean distance. Note that point x does not have to already exist in P, which differentiates this problem from the searching algorithms from Chapter 5. These queries also extend to input sets whose points are found in ndimensional space.
The naïve implementation is to inspect all points in P, resulting in a linear O(n) algorithm. Because P is known in advance, perhaps there is some way to structure its information to speed up queries by discarding large groups of its points during the search. Perhaps we could partition the plane into k^{2} bins of some fixed size m by m, as shown in Figure 101(a). Here 10 input points in P (shown as circles) are placed into nine enclosing bins. The large shaded number in each bin reflects the number of points in it. When searching for the closest neighbor for a point x (shown as a small black square), find its enclosing bin. If that bin is not empty, we only need to search the bins that intersect the focus circle whose radius is m*sqrt(2)
Figure 101. Bin approach for locating nearest neighbor
In this example, however, there are no points in the target bin, and the three neighboring bins will need to be examined. This ineffective approach is inappropriate because many bins may in fact be empty, and the algorithm would still have to search multiple neighboring bins. As we saw inChapter 5, binary trees reduce the search by eliminating from consideration groups of points that could not be part of the solution. In this chapter we introduce the idea of a spatial tree to partition the points in the twodimensional plane to reduce the search time. The extra cost of preprocessing all points in P into an efficient structure is recouped later by savings of the query computations, which become O(log n). If the number of searches is small, then the obvious O(n) comparison is best.
Range Queries
Instead of searching for a specific target point, a query could instead request all points in P that are contained within a given rectangular region of the twodimensional plane. The obvious solution requires one to determine whether the target rectangular region contains each point in the set, resulting in O(n) performance.
The same data structure developed for nearestneighbor queries also supports these queries, known as “orthogonal range” because the rectangular query region is aligned with the x and y axes of the plane. The only way to produce better than O(n) performance is to find a way to both discard points from consideration, and include points in the query result. Using a kdtree, the query is performed using a recursive traversal, and the performance can be O(n^{0.5} + r) where r is the number of points reported by the query.
Intersection Queries
The input set being searched can typically be more complicated than a single n dimensional point. Consider instead a set of rectangles R in a twodimensional plane where each rectangle r_{i} is defined by a tuple (xlow, ylow, xhigh, yhigh). With this set R you might want to locate all rectangles that intersect a given point (x, y) or (more generally) intersect a target rectangle (x_{1}, y_{1}, x_{2}, y_{2}). Structuring the rectangles appears to be more complicated because the rectangles can overlap each other in the plane.
Instead of providing a target rectangle, one might be interested in identifying the intersections among a collection of twodimensional elements. This is known as the collision detection problem, and we present a solution to detect intersections among a collection of points, P, using a squarebased regions centered around each point.
Spatial Tree Structures
Spatial tree structures offer a way to represent data to efficiently support the execution of these three common searches. In this chapter we present a number of spatial tree structures that have been used to partition ndimensional objects to improve the performance of search, insert and delete.
KDTree
In Figure 102(a), the same 10 points from Figure 101 are shown in a kdtree, so named because it can subdivide a kdimensional plane along the perpendicular axes of the coordinate system. The structure of the kdtree from Figure 102(a) is depicted as a binary tree in Figure 102(b). For the remainder of this discussion we assume a twodimensional tree, but the approach can be used for arbitrary dimensions.
Figure 102. Division of twodimensional plane using kdtree
A kdtree is a recursive binary tree structure where each node contains a point and a coordinate label (i.e., either x or y) that determines the partitioning orientation. The root node represents the rectangular region [x_{low} = ∞, y_{low} =∞, x_{high} =+∞, y_{high} = +∞] in the plane partitioned along the vertical line V through point p_{1}. The left subtree further partitions the region to the left of V, whereas the right subtree further partitions the region to the right of the V. The left child of the root represents a partition along the horizontal line H through p_{2} that subdivides the region to the left ofV into a region above the line H and a region below the line H. The region [∞,∞, p_{1}.x,+∞] is associated with the left child of the root, whereas the region [p_{1}.x,∞, +∞,+∞] is associated with the right child of the root. These regions are effectively nested, and one can see that the region of an ancestor node wholly contains the regions of any of its descendant nodes.
Quad Tree
A quadtree partitions a set of twodimensional points, P, recursively subdividing the overall space into four quadrants. It is a treelike structure where each internal node has four children, labeled NE (NorthEast), NW (NorthWest), SW (SouthWest), SE (SouthEast). Each internal node in a quadtree can have four children. There are two distinct flavors of quadtrees.
Regionbased
Given a 2^{k} by 2^{k} image of pixels where each pixel is 0 or 1, the root of a quadtree represents the entire image. Each of the four children of the root represents a 2^{k1} by 2^{k1} quadrant of the original image. If one of these four regions is not entirely 0s or 1s, then the region is subdivided into subregions, each of which is onequarter the size of its parent. Leaf nodes represent a square region of pixels that are all 0s or 1s. Figure 103 describes the tree structure with a sample image bitmap.
Figure 103. Quadtree using Regionbased partitioning
Pointbased
Given a 2^{k} by 2^{k} space in the Cartesian plane, the quadtree directly maps to a binary tree structure, where each node can store up to four points. If a point is added to a full region, the region is subdivided into four regions each onequarter the size of its parent. When no points are present in a quadrant for a node, then there is no child node for that quadrant, and so the shape of the tree depends on the order that the points were added to the quadtree.
For this chapter we focus on pointbased quadtrees. Figure 104 shows an example containing thirteen points in a 256 x 256 region. The quadtree structure is shown on the right side of the image. Note that there are no points in the root’s SouthEast quadrant, so the root only has three children nodes. Also note the variable subdivisions of the regions based upon which points have been added to the quadtree.
Figure 104. Quadtree using Pointbased partitioning
RTree
An RTree is a tree structure in which each node contains up to M links to children nodes. All actual information is stored by the leaf nodes, each of which can store up to M different rectangles. Figure 105 depicts an RTree where M=4 and five rectangles have been inserted. The result is the tree shown on the right where the interior nodes reflect different rectangular regions inside of which the actual rectangles exist.
Figure 105. RTree example
The root node represents the smallest rectangular region [x_{low}, y_{low}, x_{high}, y_{high}] that includes all other rectangles in the tree. Interior nodes have associated rectangular regions that are similarly the smallest rectangular region that includes all rectangles in descendant nodes. The actual rectangles in the RTree are stored only in leaf nodes. Aside from the root node, every rectangular region (whether associated with an interior node or a leaf node) is wholly contained by the region of its parent node.
Nearest Neighbor
Given a set of twodimensional points, P, you are asked to determine which point in P is closest to a target query point, x. We show how to use kdtrees to efficiently perform these queries. Assuming that the tree does a good job in partitioning the points, each recursive traversal through the tree will discard roughly half of the points in the tree. In a kdtree for points distributed in a normal manner, nodes on level i reflect rectangles that are roughly twice as large as the rectangles on level i+1. This property will enable Nearest Neighbor to efficiently complete in O(log n) performance because it will be able to discard entire subtrees containing points that are demonstrably too far to be the closest point. However, the recursion is a bit more complex than with the regular binary tree searching as we explain.
NEAREST NEIGHBOR SUMMARY
Best,Average: O(log n) Worst: O(n)
nearest (T, x)
n = find parent node in T where x would have been inserted
min = distance from x to n.point
better = nearest (T.root, min, x)
if better found then return better
return n.point
end
nearest (node, min, x)
d = distance from x to node.point
if d < min then
result = node.point
min = d
dp = perpendicular distance from x to node
if dp < min then
pt = nearest (node.above, min, x)
if distance from pt to x < min then
result = pt
min = distance from pt to x
pt = nearest (node.below, min, x)
if distance from pt to x < min then
result = pt
min = distance from pt to x
else
if node is above x then
pt = nearest (node.above, min, x)
else
pt = nearest (node.below, min, x)
if pt exists then return pt
return result
end
Choose reasonable best guess for closest point
Traverse again from root to try to find better one
Found closer point
If too close to call, check both above and below subtrees
Otherwise can safely check only one subtree
As shown in Figure 106, if the target point were inserted, it would become a child of the node associated with point 9. Upon calling nearest with this selection, the algorithm can discard the entire left subtree because the perpendicular distance dp is not closer, so none of those points can be closer. Recursing into the right subtree, the algorithm detects point 3 is closer. Further, it determines that the perpendicular distance to point 3 is closer than min so it must recursively investigate both the subtrees rooted at points 7 and 8. Ultimately it determines point 3 is the closest point.
Figure 106. Nearest Neighbor example
Input/Output
The input is a kdtree formed from a set of twodimensional points P in a plane. A set of nearest neighbor queries (not known in advance) is issued one at a time to find the nearest point in P to a point x.
For each query point x, the algorithm computes a point in P that is the closest neighbor to x.
If two points are “too close” to each other through floatingpoint error, the algorithm may incorrectly select the wrong point; however, the distance to the actual closest point would be so close that there should be no impact by this faulty response.
Context
When comparing this approach against a bruteforce approach that compares the distances between query point x and each point p ∈ P, there are two important costs to consider: (1) the cost of constructing the kdtree, and (2) the cost of locating the query point x within the tree structure. The tradeoffs that impact these costs are:
Number of dimensions
As the number of dimensions increases, the cost of constructing the kdtree overwhelms its utility. Some authorities believe that for morenthan 20 dimensions, this approach is less efficient than a straight comparison against all points.
Number of points in the input set
When the number of points is small, the cost of constructing the structure may outweigh the improved performance.
Binary trees can be efficient search structures because they can be balanced as nodes are inserted into and deleted from the tree. Unfortunately, kdtrees cannot be balanced easily, because of the deep structural information about the dimensional plane that they represent. The ideal solution is to construct the initial kdtree so that either (a) the leaf nodes are at the same level in the tree, or (b) all leaf nodes are within one level of all other leaf nodes.
Solution
Given an existing kdtree, Nearest Neighbor implementation is shown in Example 101.
Example 101. Nearest Neighbor Queries implemented with kdtree (method in KDTree)
public IMultiPoint nearest (IMultiPoint target) {
if (root == null) return null;
// Find parent node to which target would have been inserted.
// Best shot at finding closest point
DimensionalNode parent = parent(target);
IMultiPoint result = parent.point;
double smallest = target.distance(result);
// Start back at the root to try to find closer one
double best[] = new double[] { smallest };
double raw[] = target.raw();
IMultiPoint betterOne = root.nearest (raw, best);
if (betterOne != null) { return betterOne; }
return result;
}
// DimensionalNode method. min[0] is best computed shortest distance.
IMultiPoint nearest (double[] rawTarget, double min[]) {
// Update minimum if we are closer.
IMultiPoint result = null;
// If shorter, update minimum
double d = shorter(rawTarget, min[0]);
if (d >= 0 && d < min[0]) {
min[0] = d;
result = point;
}
// determine if we must dive into the subtrees by computing direct
// perpendicular distance to the axis along which node separates
// the plane. If d is smaller than the current smallest distance,
// we could "bleed" over the plane so we must check both.
double dp = Math.abs(coord — rawTarget[dimension1]);
IMultiPoint newResult = null;
if (dp < min[0]) {
// must dive into both. Return closest one.
if (above != null) {
newResult = above.nearest (rawTarget, min);
if (newResult != null) { result = newResult; }
}
if (below != null) {
newResult = below.nearest(rawTarget, min);
if (newResult != null) { result = newResult; }
}
} else {
// only need to go in one! Determine which one now.
if (rawTarget[dimension1] < coord) {
if (below != null) {
newResult = below.nearest (rawTarget, min);
}
} else {
if (above != null) {
newResult = above.nearest (rawTarget, min);
}
}
// Use smaller result, if found.
if (newResult != null) { return newResult; }
}
return result;
}
The key to understanding Nearest Neighbor is that we first locate the region where the target point would have been inserted, since this will likely contain the closest point. We then validate this assumption by recursively checking from the root back down to this region to see whether some other point is actually closer. (This could easily happen because the rectangular regions of the kdtree were created based upon the set of input points.) In unbalanced kdtrees, this checking process might incur an O(n) total cost, reinforcing the notion that the input set must be properly processed.
The example solution has two improvements to speed up its performance. First, the comparisons are made on the “raw” double array representing each point. Second, a shorter method in DimensionalNode is used to determine when the distance between two ddimensional points is smaller than the minimum distance computed so far; this method exits immediately when a partial computation of the Euclidean distance exceeds the minimum found.
Assuming the initial kdtree is balanced, the search can advantageously discard up to half of the points in the tree during the recursive invocations. Two recursive invocations are sometimes required, but only when the computed minimum distance is just large enough to cross over the dividing line for a node, in which case both sides need to be explored to find the closest point.
Analysis
The kdtree is initially constructed as a balanced kdtree, where the dividing line on each level is derived from the median of the points remaining at that level. Locating the parent node of the target query can be found in O(log n) by traversing the kdtree as if the point were to be inserted. However, the algorithm may make two recursive invocations: one for the child above and one for the child below.
If the double recursion occurs frequently, the algorithm degrades to be O(n), so it is worth understanding how often it can occur. The multiple invocations occur only when the perpendicular distance, dp, from the target point to the node’s point is less than the best computed minimum. As the number of dimensions increases, there are more potential points that satisfy these criteria.
Table 101 provides some empirical evidence to show how often this occurs. A balanced kdtree is created from n=4 to 131,072 random twodimensional points generated within the unit square. A set of 50 nearest point queries is issued for a random point within the unit square, and Table 101 records the average number of times two recursive invocations occurred (that is, when dp < min[0] and the node in question has childen both above and below), as compared to single recursive invocations.
Table 101. Ratio of double recursion invocations to single
n 
d=2 #Recursions 
d=2 #Double recursion 
d=10 #Recursion 
d=10 #Double recursion 
4 
1.96 
0.52 
1.02 
0.98 
8 
3.16 
1.16 
1.08 
2.96 
16 
4.38 
1.78 
1.2 
6.98 
32 
5.84 
2.34 
1.62 
14.96 
64 
7.58 
2.38 
5.74 
29.02 
128 
9.86 
2.98 
9.32 
57.84 
256 
10.14 
2.66 
23.04 
114.8 
512 
12.28 
2.36 
53.82 
221.22 
1,024 
14.76 
3.42 
123.18 
403.86 
2,048 
16.9 
4.02 
293.04 
771.84 
4,096 
15.72 
2.28 
527.8 
1214.1 
8,192 
16.4 
2.6 
1010.86 
2017.28 
16,384 
18.02 
2.92 
1743.34 
3421.32 
32,768 
20.04 
3.32 
2858.84 
4659.74 
65,536 
21.62 
3.64 
3378.14 
5757.46 
131,072 
22.56 
2.88 
5875.54 
8342.68 
From this random data, the number of double recursions appears to be .3*log(n) for two dimensions, but this jumps to 342*log(n) for 10 dimensions (a 1,000fold increase). The important observation is that both of these estimation functions conform to O(log n).
But what happens when d increases to be “sufficiently close” to n in some way? The data graphed in Figure 107 shows that as d increases, the number of double recursions actually approaches n/2. In fact, as d increases, the number of single recursions conforms to a normal distribution whose mean is very close to log(n), which tells us that eventually all recursive invocations are of the double variety. The impact this discovery has on the performance of nearest neighbor queries is that as d approaches log(n), the investment in using kdtrees begins to diminish until the resulting performance is no better than O(n), because the number of double recursions plateaus at n/2.
Figure 107. Number of double recursions as n and d increase
Certain input set data sets force Nearest Neighbor to work hard even in two dimensions. For example, let’s change the input for Table 101 such that the n unique twodimensional points are found on a unit circle of radius r>1, but the nearest query points still lie within the unit square. Whenn=131,072 points, the number of single recursions has jumped 10fold to 235.8 while the number of double recursions has exploded to 932.78 (a 200fold increase!). Thus, the nearest neighbor query will degenerate in the worst case to O(n) given specifically tailored queries for a given input set. Figure 108 demonstrates a degenerate kdtree with 64 points arranged in a circle.
Figure 108. Circular data set leads to inefficient kdtree
We can also evaluate the performance of kdtree Nearest Neighbor against a straight brute force O(n) comparison. Given a data set of size n=131,072 points, where 128 searches random are to be executed, how large must the dimensionality d of the input set be before the brute force Nearest Neighbor implementation outperforms the kdtree implementation? We ran 100 trials and discarded the best and worst trials, computing the average of the remaining 98 trials. The results are graphed in Figure 109 and show that for d=11 dimensions and higher, the bruteforce nearest neighbor implementation outperforms the Nearest Neighbor kdtree algorithm. The specific crossover point depends upon the machine hardware on which the code executes, the specific values of n and d, and the distribution of points in the input set. We do not include in this crossover analysis the cost of constructing the kdtree, because that cost can be amortized across all searches.
Figure 109. Comparing kdtree versus bruteforce implementation
The results in Figure 109 confirm that as the number of dimensions increases, the benefit of using Nearest Neighbor over brute force decreases. The cost of constructing the kdtrees is not a driving factor in the equation, because that is driven primarily by the number of data points to be inserted into the kdtree, not by the number of dimensions. On larger data set sizes, the savings is more pronounced. Another reason for the worsening performance as d increases is that computing the Euclidean distance between two ddimensional points is an O(d) operation: these computations simply takes more time.
To maximize the performance of kdtree searches, the tree must be balanced. Example 102 demonstrates the wellknown technique that uses recursion to iterate over each of the coordinate dimensions. Simply put, it selects the median element from a set of points to represent the node; and the elements below the median are inserted into the below subtree, whereas elements above the median are inserted into the above subtree. The code works for arbitrary dimensions.
Example 102. Recursively construct a balanced kdtree
public class KDFactory {
// Known comparators for partitioning points along dimensional axes.
private static Comparator<IMultiPoint> comparators[];
// Recursively construct KDTree using median method on input points.
public static KDTree generate (IMultiPoint []points) {
if (points.length == 0) { return null; }
// median will be the root.
int maxD = points[0].dimensionality();
KDTree tree = new KDTree(maxD);
// Make dimensional comparators that compare points by ith dimension
comparators = new Comparator[maxD+1];
for (int i = 1; i <= maxD; i++) {
comparators[i] = new DimensionalComparator(i);
}
tree.setRoot(generate (1, maxD, points, 0, points.length1));
return tree;
}
// generate the node for the dth dimension (1 <= d <= maxD)
// for points[left, right]
private static DimensionalNode generate (int d, int maxD,
IMultiPoint points[],
int left, int right) {
// Handle the easy cases first
if (right < left) { return null; }
if (right == left) { return new DimensionalNode (d, points[left]); }
// Order the array[left,right] so the mth element will be the
// median and the elements prior to it will all be <= median,
// though they won't necessarily be sorted; similarly, the elements
// after will all be >= median
int m = 1+(rightleft)/2;
Selection.select(points, m, left, right, comparators[d]);
// Median point on this dimension becomes the parent
DimensionalNode dm = new DimensionalNode (d, points[left+m1]);
// update to the next dimension, or reset back to 1
if (++d > maxD) { d = 1; }
// recursively compute left and right subtrees, which translate
// into 'below' and 'above' for ndimensions.
dm.setBelow(maxD, generate (d, maxD, points, left, left+m2));
dm.setAbove(maxD, generate (d, maxD, points, left+m, right));
return dm;
}
}
The select operation was described in Chapter 4. It can select the k^{th} smallest number recursively in O(n) time in the average case; however, it does degrade to O(n^{2}) in the worst case.
Variations
In the implementation we have shown, the method nearest traverses from the root back down to the computed parent; alternate implementations start from the parent and traverse back to the root, in bottomup fashion.
Range Query
Given a rectangular range R defined by [x_{low}, y_{low}, x_{high}, y_{high}] and a set of points P, which points in P are contained within a target rectangle t? A bruteforce algorithm that inspects all points in P can determine the enclosed points in O(n)—can we do better?
For Nearest Neighbor, we organized the points into a kdtree to process nearest neighbor queries in O(log n) time. Using the same data structure, we now show how to compute Range Query in O(n^{0.5} + r), where r is the number of points reported by the query. Indeed, when the input set contains ddimensional data points, the solution scales to solve ddimensional Range Query problems in O(n^{11/d}+r).
RANGE QUERY SUMMARY
Best, Average: O(n^{11/d}+r) Worst: O(n)
range (space)
results = new Set
range (space, root, results)
return results
end
range (space, node, results)
if space contains node.region then
add node.points andall of its descendants to results
return
if space contains node.point then
add node.point to results
if space extends below node.coord then
range (space, node.below, results)
if space extends above node.coord then
range (space, node.above, results)
end
Should a kdtree node be wholly contained by search space, all descendants are added to results
Ensure point is added to results if contained
May have to search both above and below
Figure 1010. Range Query example
Input/Output
The input is a set of n points P in ddimensional space and a ddimensional hypercube that specifies the desired range query. The range queries are aligned properly with the axes in the ddimensional data set because they are specified by d individual ranges, for each dimension of the input set. For d = 2, this means the range query has both a range over x coordinates and a range over y coordinates.
Range Query generates the full set of points enclosed by the range query. The points do not appear in any specific order.
Context
Kdtrees become unwieldy for a large number of dimensions, so this algorithm and overall approach should be restricted to small dimensional data. For two dimensional data, kdtrees offers excellent performance for Nearest Neighbor and Range Query problems.
Solution
The Java solution shown in Example 103 is a method of the DimensionalNode class, which is simply delegated by the range(IHypercube) method found in KDTree. The key efficiency gain of this algorithm occurs when the region for a DimensionalNode is wholly contained within the desired range query. In this circumstance, all descendant nodes of the DimensionalNode can be added to the results collection because of the kdtree property that the children for a node are wholly contained within the region of any of its ancestor nodes.
Example 103. Range Query implementation
public void range (IHypercube space, KDSearchResults results) {
// Wholly contained? Take all descendant points
if (space.contains (region)) {
results.add(this);
return;
}
// Is our point at least contained?
if (space.intersects (cached)) {
results.add(point);
}
// Recursively progress along both ancestral trees, if demanded.
// The cost in manipulating space to be "cropped" to the proper
// structure is excessive, so leave alone and is still correct.
if (space.getLeft(dimension) < coord) {
if (below != null) { below.range(space, results); }
}
if (coord < space.getRight(dimension)) {
if (above != null) { above.range(space, results); }
}
}
The code shown in Example 103 is a modified tree traversal that potentially visits every node in the tree. Because the kdtree partitions the ddimensional data set in hierarchical fashion, there are three decisions Range Query makes at each node n:
Is the region associated with node n fully contained within the query region?
When this happens, the range traversal can stop because all descendant points belong to the query result.
Does the query region contain the point associated with node n?
If so, add the point associated with n to the result set.
Along the dimension d represented by node n, does query region intersect n?
It can do so in two ways: if the query region seeks points to the left of d, traverse the below subtree of n. If the query region seeks points to the right of d, traverse the above subtree.
Analysis
It is possible that the query region contains all points in the tree, in which case all points are returned which leads to O(n) performance. However, when Range Query detects that the query region does not intersect an individual node within the kdtree, it can prune the traversal. The cost savings depend upon the number of dimensions and the specific nature of the input set. Preparata and Shamos (1985) showed that Range Query using kdtrees performs in O(n^{11/d}+r), where r is the number of results found. As the number of dimensions increases, the benefit decreases.
Figure 1011 graphs the expected performance of an O(n^{11/d}) algorithm; the distinctive feature of the graph is fast performance for small values of d that over time inexorably approaches O(n). Because of the addition of r (the number of points returned by the query), the actual performance will deviate from the ideal curve shown in Figure 1011.
Figure 1011. Expected performance for O(n^{11/d}) algorithm
It is difficult to produce sample data sets to show the performance of Range Query. We demonstrate the effectiveness of Range Query on a kdtree by comparing its performance to a bruteforce implementation that inspects each point against the desired query region. The ddimensional input set for each of these situations contains n points whose coordinate values are drawn uniformly from the range [0,s], where s=4,096. We evaluate three situations:
Query region contains all points in the tree
We construct a query region that contains all of the points in the kdtree. This example provides the maximum speedup supported by the algorithm; its performance is independent of the number of dimensions d in the kdtree. The kdtree approach takes about 57 times as long to complete; this represents the overhead inherent in the kdtree structure. In Table 102, the performance cost for the bruteforce region query increases as d increases because computing whether a ddimensional point is within a ddimensional space is an O(d) operation, not constant. The brute force implementation handily outperforms the kdtree implementation.
Table 102. Comparing Range Query execution times in milliseconds (kdtree versus brute force) for All Points scenario
n 
d=2 RQ 
d=3 RQ 
d=4 RQ 
d=5 RQ 
d=2 BF 
d=3 BF 
d=4 BF 
d=5 BF 
4,096 
6.22 
13.26 
19.6 
22.15 
4.78 
4.91 
5.85 
6 
8,192 
12.07 
23.59 
37.7 
45.3 
9.39 
9.78 
11.58 
12 
16,384 
20.42 
41.85 
73.72 
94.03 
18.87 
19.49 
23.26 
24.1 
32,768 
42.54 
104.94 
264.85 
402.7 
37.73 
39.21 
46.64 
48.66 
65,536 
416.39 
585.11 
709.38 
853.52 
75.59 
80.12 
96.32 
101.6 
131,072 
1146.82 
1232.24 
1431.38 
1745.26 
162.81 
195.87 
258.6 
312.38 
Fractional regions
Because the number of results found, r, plays a prominent role in determining the performance of the algorithm, we construct a set of scenarios to isolate this variable as the number of dimensions increases.
The uniformity of the input set discourages us from simply constructing a query region [.5*s, s] for each dimension of input. If we did this, the total volume of the input set queried is (1/2)^{d}, which implies that as d increases the number of expected points, r, returned by the query region decreases. Instead, we construct query regions whose size increases as d increases. For example, in two dimensions the query region with [.5204*s, s] on each dimension should return .23*n points because (1.5204)^{2}=.23. However, for three dimensions the query region must expand to [.3873*s, s] on each dimension since (1.3873)^{3}=.23.
Using this approach, we fix in advance the desired ratio k such that our constructed query will return k*n points (where k is either .23, .115, 0.0575, 0.02875 or 0.014375). We compare the kdtree implementation against a brute force implementation as n varies from 4,096 to 131,072 and dvaries from 2 to 15, as shown in Figure 1012. The charts on the left side show the distinctive behavior of the O(n^{11/d}) kdtree algorithm while the right side shows the linear performance of brute force. For a 0.23 ratio, the kdtree implementation outperforms brute force only for d=2 and n ≤ 8,192; however, for a ratio of 0.014375, the kdtree implementation wins for d ≤ 6 and n ≤ 131,072.
Figure 1012. Comparing kdtree versus brute force for Fractional Region
Empty region
We construct a query region from a single random point drawn uniformly from the same values for the input set. Performance results are shown in Table 103. The kdtree executes nearly instantaneously; all recorded execution times are less than a fraction of a millisecond.
Table 103. Brute force Range Query execution times in milliseconds for Empty Region
n 
d=2 BF 
d=3 BF 
d=4 BF 
d=5 BF 
4,096 
3.36 
3.36 
3.66 
3.83 
8,192 
6.71 
6.97 
7.3 
7.5 
16,384 
13.41 
14.02 
14.59 
15.16 
32,768 
27.12 
28.34 
29.27 
30.53 
65,536 
54.73 
57.43 
60.59 
65.31 
131,072 
124.48 
160.58 
219.26 
272.65 
QuadTrees
Quadtrees can be used to solve the following queries:
Range Queries
Given a collection of points in the Cartesian plane, determine the points that exist within a query rectangle. A sample application is shown in Figure 1013 where a dashed rectangle is selected by the user, and points contained within the rectangle are drawn in red. When a quadtree region is wholly contained by the target query then the application draws that region with shaded background.
Figure 1013. Range searching using a quadtree
Collision Detection
Given a collection of objects in the Cartesian plane, determine all intersections among the objects. A sample application is shown in Figure 1013 that identifies the collisions among a number of moving squares that bounce back and forth within a window. Squares that intersect each other are drawn in red.
Figure 1014. Collision detection using a quadtree
QUADTREE SUMMARY
Best, Average, Worst: O(log n)
add (node, pt)
if node.region does notcontain pt then
return False
if node is leaf node then
if node already contains pt then
return False
if node has < 4 points then
add pt to node
return True
q = quadrant for pt in node
if node is leaf node then
node.subdivide()
return add(node.children[q], pt)
range (node, rect, result)
if rect contains node.region then
add (node, True) to result
else if node is leaf node then
for all points p in node do
if rect contains pt then
add (pt, False) to result
else
for child in node.children do
if rect overlaps child.region
range(child, rect, result)
Impose set semantics on quadtree
Each node can store up to 4 points
Leaf points distributed among 4 new children
Insert new point into correct child
Entire subtree is contained and returned
Individual points returned
Recursively check each overlapping child
Input/Output
The input is a set of twodimensional points P in a plane, from which a quadtree is constructed.
For optimal performance, range queries return the nodes in the quadtree, which allows it to return entire subtrees of points when the target rectangle wholly contains a subtree of points. The results of a collision detection are the existing points that intersect with a target point.
Solution
The basis of the Python implementation of quadtree is the QuadTree and QuadNode structures shown in Example 104. The smaller2k and larger2k helper methods ensure that the initial region has sides that are powers of two. The Region class represents a rectangular region.
Example 104. Quadtree QuadNode implementation
class Region:
def __init__(self, xmin,ymin, xmax,ymax):
"""
Creates region from two points (xmin,ymin) to (xmax,ymax). Adjusts if these
are not the bottom left and top right coordinates for a region.
"""
self.x_min = xmin if xmin < xmax else xmax
self.y_min = ymin if ymin < ymax else ymax
self.x_max = xmax if xmax > xmin else xmin
self.y_max = ymax if ymax > ymin else ymin
class QuadNode:
def __init__(self, region, pt = None, data = None):
"""Create empty QuadNode centered on origin of given region."""
self.region = region
self.origin = (region.x_min + (region.x_max  region.x_min)//2,
region.y_min + (region.y_max  region.y_min)//2)
self.children = [None] * 4
if pt:
self.points = [pt]
self.data = [data]
else:
self.points = []
self.data = []
class QuadTree:
def __init__(self, region):
"""Create empty QuadTree over square region whose sides are powers of 2."""
self.root = None
self.region = region.copy()
minPower = min(smaller2k(self.region.x_min), smaller2k(self.region.y_min))
self.region.x_min = self.region.y_min = minPower
maxPower = max(larger2k(self.region.x_max), larger2k(self.region.y_max))
self.region.x_max = self.region.y_max = maxPower
Points are added to the quadtree using the add methods shown in Example 105. The add method returns False if the point is already contained within the quadtree, thus it enforces mathematical set semantics. Up to four points are added to a node if the point is contained within that node’s rectangular region. When the fifth point is added to a node, the node’s region is subdivided into quadrants and the points are reassigned to the individual quadrants of that node’s region; should all points be assigned to the same quadrant, the process repeats until the points can all be added to a quadrant such that no quadrant has more than four points.
Example 105. Quadtree add implementation
class QuadNode:
def add (self, pt, data):
"""Add (pt, data) to the QuadNode."""
node = self
while node:
# Not able to fit in this region
if notcontainsPoint(node.region, pt):
return False
# if we have points, then we are leaf node. Check here
if node.points != None:
if pt innode.points:
return False
# Add if room
if len(node.points) < 4:
node.points.append(pt)
node.data.append(data)
return True
# Find quadrant into which to add
q = node.quadrant(pt)
if node.children[q] isNone:
# subdivide and reassign points to each quadrant. Then add point
node.subdivide(node.points, node.data)
node.points = None
node.data = None
node = node.children[q]
return False
class QuadTree:
def add(self, pt, data = None):
if self.root isNone:
self.root = QuadNode(self.region, pt, data)
return True
return self.root.add(pt, data)
With this structure, the range method in Example 106 demonstrates how to efficiently locate all points in the quadtree that are contained by a target region. This Python implementation uses the yield operator to provide an iterator interface to the results. The iterator contains tuples that are either individual points or entire nodes. When a quadtree node is wholly contained by a region, that entire node is returned as part of the result. The caller can retrieve all descendant values using a preorder traversal of the node, provided by QuadNode.
Example 106. Quadtree Range Query implementation
class QuadNode:
def range(self, region):
"""
Yield (node,True) when node contained within region,
otherwise (region,False) for all points.
"""
if region.containsRegion(self.region):
yield (self, True)
else:
# if we have points, then we are leaf node. Check here
if self.points != None:
for i inrange(len(self.points)):
if containsPoint(region, self.points[i]):
yield ((self.points[i], self.data[i]), False)
else:
for child inself.children:
if child.region.overlap(region):
for pair inchild.range(region):
yield pair
class QuadTree:
def range(self, region):
"""Yield (node,status) in Quad Tree contained within region."""
if self.root isNone:
return None
return self.root.range(region)
To support collision detection, Example 107 contains the collide method which searches through the quadtree to locate
Example 107. Quadtree Collision Detection implementation
class QuadNode:
def collide (self, pt, r):
"""Yield points in leafnode that intersect with point and square side r."""
node = self
while node:
# Not able to fit in this region
if containsPoint(node.region, pt):
# if we have points, then we are leaf node. Check here
if node.points != None:
for p,d inzip(node.points,node.data):
if p[X]  r <= pt[X] <= p[X] + r andp[Y]  r <= pt[Y] <= p[Y] + r:
yield (p,d)
# Find quadrant into which to check further
q = node.quadrant(pt)
node = node.children[q]
class QuadTree:
def collide(self, pt, r):
"""Return collisions to point within Quad Tree."""
if self.root isNone:
return None
return self.root.collide(pt, r)
Analysis
Quadtrees partition the points in a plane using the same underlying structure of binary search trees. The regionbased implementation presented here uses a fixed partitioning scheme which leads to efficient behavior when the collection of points is uniformly distributed. It may happen that the points are all clustered together in a small space, as shown in Figure 1015. Thus the search performance is logarithmic with respect to the tree size. The range query in Python is made efficient by returning both individual points as well as entire nodes in the quadtree; however you must still consider the time to extract all descendant values in the nodes of the nodes returned by range query.
Figure 1015. Degenerate quadtree
Variations
The quadtree structure presented here is a region quadtree. A point quadtree represents two dimensional points. The Octree extends quadtree into three dimensions, with eight children (as with a cube) instead of four.
RTrees
Balanced binary trees are an incredibly versatile data structure that offer great performance for search, insert and delete operations. However, they work best in primary memory using pointers and allocating (and releasing) nodes as needed. These trees can only grow as large as primary memory, and they are not easily stored to secondary storage, such as a file system. Operating systems provide Virtual Memory so programs can operate using an assigned memory space which might be larger than the actual memory. The operating system ensures that a fixedsize block of memory (known as a page) is brought into primary memory as needed, and older unused pages are stored to disk (if modified) and discarded. Programs work most efficiently when consolidating read and write access using pages, which are typically 4,096 bytes in size. If you consider that a node in a binary tree might only require 24 bytes of storage, there would be dozens of such nodes packed to a page. It is not immediately clear how to store these binary nodes to disk especially when the tree is dynamically updated.
The BTree concept was developed by Bayer and McCreight in 1972, though it appears to have been independently discovered by vendors of database management systems and operating systems. A BTree extends the structure of a binary tree by allowing each node to store multiple values and multiple links to more than 2 nodes. A sample 3order BTree is shown in Figure 1016.
Figure 1016. Sample BTree
Each node n contains a number of ascending values { k_{1}, k_{2}, …, k_{m1} } and pointers { p_{1}, p_{2}, …, p_{m} } where m determines the maximum number of children nodes that n can point to. The value m is known as the order of the BTree. Each BTree node can contain m1 values.
To maintain the binary search tree property, BTree nodes store key values such that all values in the subtree pointed to by p_{1} are smaller than k_{1}. All values in the subtree pointed to by p_{i} are greater than k_{i} and smaller than k_{i+1}. Finally, all values in the subtree pointed to by p_{m} are greater than k_{m1}.
Using Knuth’s definition, a BTree of order m satisfies the following:
1. Every node has at most m children
2. Every nonleaf node (except root) has at least ⌈ m⁄2 ⌉ children
3. The root has at least two children if it is not a leaf node.
4. A nonleaf node with k children nodes contains k−1 key values.
5. All leaves appear in the same level
Using this definition, a traditional binary tree is a degenerate BTree of order m=2. Insertions and deletions in a BTree must maintain these properties. In doing so, the longest path in a BTree with n keys contains at most log_{m}(n) nodes, leading to O(log n) performance for its operations. BTrees can be readily stored to secondary storage by increasing the number of keys in each node so that its total size properly aligns with the page size (i.e., storing two BTree nodes per page), which minimizes the number of disk reads to load nodes into primary memory.
With this brief sketch of BTrees, we can now describe in more detail the RTree structure. An RTree is a heightbalanced tree, similar to a BTree that stores ndimensional spatial objects in a dynamic structure that supports insert, delete and search. It also supports range queries for locating objects that overlap with a target ndimensional query. In this chapter, we describe the fundamental operations that maintain RTrees to ensure efficient execution of the core operations.
An RTree is a tree structure in which each node contains links to up to M different children nodes. All information is stored by the leaf nodes, each of which can store up to M different ndimensional spatial objects. The RTree provides an index into the actual repository that stores the objects themselves; the RTree only stores the unique identifier for each object and the ndimensional bounding box, I, which is the smallest ndimensional shape that contains the spatial object. In this presentation we assume twodimensions and these shapes are rectangles, but it can naturally be extended to n dimensions based on the structure of the data.
There is another relevant constant, m ≤ M/2, which defines the minimum number of values stored by a leaf node or links stored by interior nodes in the RTree. We summarize the RTree properties below:
1. Every leaf node contains between m and M (inclusive) records [unless it is the root]
2. Every nonleaf node contains between m and M (inclusive) links to children nodes [unless it is the root]
3. For each entry (I, child_{i}) in a nonleaf node, I is the smallest rectangle that spatially contains the rectangles in its children nodes
4. The root node has at least two children [unless it is a leaf]
5. All leaves appear on the same level
The RTree is a balanced structure that ensures the above properties. For convenience, the leaf level is considered level 0, and the level number of the root node is the height of the tree. The RTree structure supports insertion, deletion and query in O(log_{m} n).
RTREE SUMMARY
Best, Average: O(log_{m} n), Worst: O(n)
add (R, rect)
if R is empty then
R = new RTree with rect
else
leaf = chooseLeaf(rect)
if leaf.count < M then
add rect to leaf
else
newLeaf = leaf.split(rect)
newNode = adjustTree (leaf, newLeaf)
if newNode != null then
R = new RTree with old Root andnewNode as children
end
search (n, t)
if n is a leaf then
return entry if n contains t otherwise False
else
foreach child c of n do
if c contains t then
return search(c,t)
end
range (n, t)
if target wholly contains n's bounding box then
return all descendant rectangles
else if n is a leaf
return all entries that intersect t
else
result = null
foreach child c of n do
if c overlaps t then
result = union of result andrange(c,t)
return result
Entries are added to a leaf node if there is room
Otherwise M+1 entries are divided among old leaf and new node
Entries in path to root may need to be adjusted
RTree might grow in height in response
Leaf nodes contain the actual entries
Recursively search each child since regions may overlap
Once found the entry is returned
Efficient operation for detecting membership
May have to execute multiple recursive queries
The repository contains sample applications for investigating the behavior of RTrees. Figure 1017 shows the dynamic behavior as a new rectangle 6 is added to the RTree that contains M=4 shapes. As you can see, there is no room for the new rectangle, so the relevant leaf node R1 is splitinto two nodes, based upon a metric that seeks to minimize the area of the respective new nonleaf nodes, R2. Adding this rectangle increases the overall height of the RTree by one since it creates a new root, R3.
Figure 1017. RTree insert example
Input/Output
A twodimensional RTree stores a collection of rectangular regions in the Cartesian plane, each with its own (optional) unique identifier.
RTree operations can modify the state of the RTree (i.e., insert or delete) as well as retrieve an individual rectangular region or a collection of regions.
Context
RTrees were designed to index multidimensional information including geographical structures or more abstract ndimensional data, such as rectangles or polygons. This is one of the few structures that offers excellent runtime performance even when the information is too large to store in main memory. Traditional indexing techniques are inherently onedimensional and so RTree structures are wellsuited for these domains.
The operations on an RTree include insertion and deletion, and there are two kinds of queries. You can search for a specific rectangular region in the RTree or you can determine the collection of rectangular regions that intersect a target query rectangle.
Solution
The following Python implementation associates an optional identifier with each rectangle; this would be used to retrieve the actual spatial object from the database. We start with the RNode which is the fundamental unit of an RTree. Each RNode maintains a bounding region and an optional identifier. An RNode is a leaf if node.level is zero. There are node.count children for an RNode and they are stored in the node.children list. When adding a child RNode, the parent node.region bounding box must be adjusted to include the newly added child.
Example 108. RTree RNode implementation
class RNode:
# Monotonically incrementing counter to generate identifiers
counter = 0
def __init__(self, M, rectangle = None, ident = None, level = 0):
if rectangle:
self.region = rectangle.copy()
else:
self.region = None
if ident isNone:
RNode.counter += 1
self.id = 'R' + str(RNode.counter)
else:
self.id = ident
self.children = [None] * M
self.level = level
self.count = 0
def addRNode(self, rNode):
"""Add previously computed RNode and adjust bounding region."""
self.children[self.count] = rNode
self.count += 1
if self.region isNone:
self.region = rNode.region.copy()
else:
rectangle = rNode.region
if rectangle.x_min < self.region.x_min:
self.region.x_min = rectangle.x_min
if rectangle.x_max > self.region.x_max:
self.region.x_max = rectangle.x_max
if rectangle.y_min < self.region.y_min:
self.region.y_min = rectangle.y_min
if rectangle.y_max > self.region.y_max:
self.region.y_max = rectangle.y_max
With this base in place, Example 109 describes the RTree class and the method for adding a rectangle to an RTree.
Example 109. RTree and corresponding add implementation
class RTree:
def __init__(self, m=2, M=4):
"""Create empty R tree with (m=2, M=4) default values."""
self.root = None
self.m = m
self.M = M
def add(self, rectangle, ident = None):
"""Insert rectangle into proper location with given (optional) identifier."""
if self.root isNone:
self.root = RNode(self.M, rectangle, None)
self.root.addEntry(self.M, rectangle, ident)
else:
# I1 [Find position for new record] Invoke ChooseLeaf to select
# a leaf node L in which to place E. Path to leaf returned
path = self.root.chooseLeaf(rectangle, [self.root]);
n = path[1]
del path[1]
# I2 [Add record to leaf node] If L has room for another entry,
# install E. Otherwise invoke SplitNode to obtain L and LL containing
# E and all the old entries of L
newLeaf = None
if n.count < self.M:
n.addEntry(self.M, rectangle, ident)
else:
newLeaf = n.split(RNode(self.M, rectangle, ident, 0), self.m, self.M)
# I3 [Propagate changes upwards] Invoke AdjustTree on L, also
# passing LL if a split was performed
newNode = self.adjustTree(n, newLeaf, path)
# I4 [Grow tree taller] If node split propagation caused the root to
# split, create a new root whose children are the two resulting nodes.
if newNode:
newRoot = RNode(self.M, level = newNode.level + 1)
newRoot.addRNode(newNode)
newRoot.addRNode(self.root)
self.root = newRoot
The comments in Example 109 reflect the steps in the algorithm published in the original 1984 RTree paper. Each RTree object records the configured m and M values and the root RNode object of the tree. Adding the first rectangle to an empty RTree simply creates the initial structure; thereafter, the add method finds an appropriate leaf node into which to add the new rectangle. The computed path list returns the ordered nodes from the root to the selected leaf node.
If there is enough room in the selected leaf node, then the new rectangle is added to it and the bounding box changes are propagated up to the root using the adjustTree method. If, however, the selected leaf node is full, a newLeaf node is constructed and the M+1 entries are split betweenn and newLeaf using a strategy to minimize the total area of the bounding boxes of these two nodes. In this case, the adjustTree method must also propagate the new structure upwards to the root, which might further cause other nodes to be split in similar fashion. If the original root nodeself.root is split, then a new root RNode is created to be the parent of the original root and the newly created RNode object. Thus an RTree grows by only one level because existing nodes are split to make room for new entries.
Range queries can be performed as shown in Example 1010. This implementation is brief because of Python’s ability to write generator functions that behave like iterators. The recursive range method of RNode first checks whether the target rectangle wholly contains a given RNode; if so, the rectangles of all descendant leaf nodes will need to be included in the result. As a placeholder, a tuple (self, 0, True) is returned; the invoking function can retrieve all of these regions using a leafOrder generator defined by RNode. Otherwise, for nonleaf nodes, the function recursively yields those rectangles that are found in the descendants whose bounding rectangle intersects the target rectangle. Rectangles in leaf nodes are returned if the target rectangle overlaps their bounding boxes.
Example 1010. RTree/RNode implementation of Range Query
class RNode:
def range(self, target):
"""Return generator (node,0,True) or (rect,id,False)
of all qualifying identifiers overlapping target."""
# Wholly contained for all interior nodes? Return entire node
if target.containsRegion(self.region):
yield (self, 0, True)
else:
# check leaves and recurse
if self.level == 0:
for idx inrange(self.count):
if target.overlaps(self.children[idx].region):
yield (self.children[idx].region, self.children[idx].id, False)
else:
for idx inrange(self.count):
if self.children[idx].region.overlaps(target):
for triple inself.children[idx].range(target):
yield triple
class RTree:
def range(self, target):
"""Return generator of all qualifying (node,0,True) or
(rect,id,False) overlapping target."""
if self.root:
return self.root.range(target)
else:
return None
Searching for an individual rectangle has the same structure as the code in Example 1010; only the RNode search function is shown in Example 1011. This function returns the rectangle and the optional identifier used when inserting the rectangle into the RTree.
Example 1011. RNode implementation of search query
class RNode:
def search(self, target):
"""Yield (rectangle,id) if node contains target rectangle."""
if self.level == 0:
for idx inrange(self.count):
if target == self.children[idx].region:
yield (self.children[idx].region, self.children[idx].id)
elif self.region.containsRegion(target):
for idx inrange(self.count):
if self.children[idx].region.containsRegion(target):
for pair inself.children[idx].search(target):
yield pair
To complete the implementation of RTrees, we’ll need the ability to delete a rectangle that exists in the tree. Whereas the add method had to split nodes that were too full, the remove must process nodes that have too few children, given the minimum number of children nodes, m. The key idea is that once a rectangle is removed from the RTree, any of the nodes from its parent node to the root might become “underfull.” The implementation shown in Example 1012 handles this using a helper method, condenseTree, which returns a list of “orphaned” nodes with fewer than mchildren; these values are reinserted into the RTree once the remove request completes.
Example 1012. RNode implementation of remove operation
class RTree:
def remove(self, rectangle):
"""Remove rectangle value from R Tree."""
if self.root isNone:
return False
# D1 [Find node containing record] Invoke FindLeaf to locate
# the leaf node n containing R. Stop if record not found.
path = self.root.findLeaf(rectangle, [self.root]);
if path isNone:
return False
leaf = path[1]
del path[1]
parent = path[1]
del path[1]
# D2 [Delete record.] Remove E from n
parent.removeRNode(leaf)
# D3 [Propagate changes] Invoke condenseTree on parent
if parent == self.root:
self.root.adjustRegion()
else:
Q = parent.condenseTree(path, self.m, self.M)
self.root.adjustRegion()
# CT6 [Reinsert orphaned entries] Reinsert all entries of nodes in set Q.
# Entries from eliminated leaf nodes are reinserted in tree leaves as in
# Insert(), but entries from higherlevel nodes must be placed higher in
# the tree, so that leaves of their dependent subtrees will be on the same
# level as leaves of the main tree
for n inQ:
for rect,ident inn.leafOrder():
self.add(rect, ident)
# D4 [Shorten tree.] If the root node has only one child after
# the tree has been adjusted, make the child the new root
while self.root.count == 1 andself.root.level > 0:
self.root = self.root.children[0]
if self.root.count == 0:
self.root = None
return True
Analysis
The RTree structure derives its efficiency by its ability to balance itself when rectangles are inserted. Since all rectangles are stored in leaf nodes at the same height in the RTree, the interior nodes represent the bookkeeping structure. Parameters m and M determine the details of the structure, but the overall guarantee is that the height of the tree will be O(log n) where n is the number of nodes in the RTree. The split method distributes rectangles among two nodes using a heuristic that minimizes the total area of the enclosing bounding boxes of these two nodes; there have been other heuristics proposed in the literature.
The search performance of RTree methods depends upon the number of rectangles in the RTree and the density of those rectangles, or the average number of rectangles that contain a given point. Given n rectangles formed from random coordinates in the unit square, about 10% of them intersect a random point, which means the search must investigate multiple subchildren in trying to locate an individual rectangle. Specifically, it must investigate every subchild whose region overlaps the target search query. With lowdensity data sets, searching an RTree becomes more efficient.
Inserting rectangles into an RTree may cause multiple nodes to be split, which is a costly operation. Similarly, when removing rectangles from an RTree, multiple orphaned nodes must have their rectangles reinserted into the tree. Deleting rectangles is more efficient than searching because while looking for the rectangles to delete the recursive calls are limited to subchildren that wholly contain the target rectangle being deleted.
Table 104. RTree build performance on dense and sparse data sets
Dense 
Sparse 

M 
m=2 
m=3 
m=4 
m=5 
m=6 
m=2 
m=3 
m=4 
m=5 
m=6 

4 
1.32 
1.36 

5 
1.26 
1.22 

6 
1.23 
1.23 
1.2 
1.24 

7 
1.21 
1.21 
1.21 
1.18 

8 
1.24 
1.21 
1.19 
1.21 
1.2 
1.19 

9 
1.23 
1.25 
1.25 
1.2 
1.19 
1.18 

10 
1.35 
1.25 
1.25 
1.25 
1.18 
1.18 
1.18 
1.22 

11 
1.3 
1.34 
1.27 
1.24 
1.18 
1.21 
1.22 
1.22 

12 
1.3 
1.31 
1.24 
1.28 
1.22 
1.17 
1.21 
1.2 
1.2 
1.25 
Table 104 shows performance results on two rectangle data sets containing 8,100 rectangles. In these tables, we show different performance results for varying values of m and M. In the sparse set, the rectangles all have the same size but have no overlaps. In the dense set, the rectangles are formed from two random points drawn from the unit square. The entries record the total time to construct the RTree from the rectangles. The build time is slightly higher for the dense set because of the increased number of nodes that have to be split when inserting rectangles.
Table 105. RTree search performance on sparse and dense data sets
Dense 
Sparse 

M 
m=2 
m=3 
m=4 
m=5 
m=6 
m=2 
m=3 
m=4 
m=5 
m=6 

4 
25.16 
0.45 

5 
21.73 
0.48 

6 
20.98 
21.66 
0.41 
0.39 

7 
20.45 
20.93 
0.38 
0.46 

8 
20.68 
20.19 
21.18 
0.42 
0.43 
0.39 

9 
20.27 
21.06 
20.32 
0.44 
0.4 
0.39 

10 
20.54 
20.12 
20.49 
20.57 
0.38 
0.41 
0.39 
0.47 

11 
20.62 
20.64 
19.85 
19.75 
0.38 
0.35 
0.42 
0.42 

12 
19.7 
20.55 
19.47 
20.49 
21.21 
0.39 
0.4 
0.42 
0.43 
0.39 
Table 105 shows the total time to search for all rectangles in the RTree. The dense data set is about 100 times slower than the sparse set. Additionally, it shows the benefit of having the minimum number of children nodes to be m=2. Table 106 contains the corresponding performance for deleting all rectangles in the RTree. Likely the performance spikes in the dense tree set are the result of the small size of the random data set.
Table 106. RTree delete performance on sparse and dense data sets
Dense 
Sparse 

M 
m=2 
m=3 
m=4 
m=5 
m=6 
m=2 
m=3 
m=4 
m=5 
m=6 

4 
19.56 
4.08 

5 
13.16 
2.51 

6 
11.25 
18.23 
1.76 
4.81 

7 
12.58 
11.19 
1.56 
3.7 

8 
8.31 
9.87 
15.09 
1.39 
2.81 
4.96 

9 
8.78 
11.31 
14.01 
1.23 
2.05 
3.39 

10 
12.45 
8.45 
9.59 
18.34 
1.08 
1.8 
3.07 
5.43 

11 
8.09 
7.56 
8.68 
12.28 
1.13 
1.66 
2.51 
4.17 

12 
8.91 
8.25 
11.26 
14.8 
15.82 
1.04 
1.52 
2.18 
3.14 
5.91 
We now fix M=4 and m=2 and compute the performance of search and deletion as n increases in size. In general, higher values of M are beneficial when there are lots of deletions, since it reduces the number of values to be reinserted into the RTree because of underfull nodes, but the true behavior is based on the data and the balancing approach used when splitting nodes. The results are shown in Table 107.
Table 107. RTree search and delete performance (in milliseconds) on sparse data set as n doubles
n 
Search 
Delete 
128 
0.033 
0.135 
256 
0.060 
0.162 
512 
0.108 
0.262 
1,024 
0.178 
0.320 
2,048 
0.333 
0.424 
4,096 
0.725 
0.779 
8,192 
1.487 
1.306 
16,384 
3.638 
2.518 
32,768 
7.965 
3.980 
65,536 
16.996 
10.051 
131,072 
33.985 
15.115 
References
Bayer, R. and McCreight, C., “Organization and maintenance of large ordered indexes”, Acta Inf. 1, 3, 173189, 1972.
Comer, D. , “The Ubiquitous BTree”, Computing Surveys 11(2): 123–137, http://dl.acm.org/citation.cfm?id=356776, ISSN 03600300, 1979.
Guttman, A., “RTrees: Dynamic index structure for spatial searching”, Proceedings, ACM SIGMOD International Conference on Management of Data, http://dl.acm.org/citation.cfm?id=602266, pp. 4757, 1984.