Algorithms in a Nutshell

(^296) | Chapter 9: Computational Geometry
Situation 1: Query region contains all points in the tree
We construct a query region that contains all of the points in the kd-tree.
This example provides the maximum speedup supported by the algorithm; its
performance is independent of the number of dimensionsdin the kd-tree.
The kd-tree approach takes about 5–7 times as long to complete; this represents
the overhead inherent in the kd-tree structure. In Table 9-7, the performance
cost for the brute-force region query increases asdincreases because computing
whether ad-dimensional point is within ad-dimensional space is an O(d)
operation, not constant. The brute force implementation handily outperforms
the kd-tree implementation.
Situation 2: Fractional regions
Because the number of results found,r, plays a prominent role in deter-
mining the performance of the algorithm, we construct a set of scenarios to
isolate this variable as the number of dimensions increases. Because of the
uniformity of the input set, we cannot simply construct a query region [.5s,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 asdincreases the number of expected
points,r, returned by the query region decreases. Instead, we construct query
regions whose size increases asdincreases. For example, in two dimensions
the query region with [.5204s,s] on each dimension should return .23n
points since (1–.5204)^2 =.23. However, for three dimensions the query region
must expand to [.3873s,s] on each dimension since (1–.3873)^3 =.23. Using
this construction, we fix in advance the desired ratioksuch that our constructed
query will returnk*npoints (wherekranges from .23, .115, 0.0575,0.02875
and 0.014375). We compare the kd-tree implementation against a brute force
implementation asnvaries from 4,096 to 131,072 anddvaries from 2 to 15,
as shown in Figure 9-26. The charts on the left side show the distinctive
behavior of the O(n1-1/d) kd-tree algorithm while the right side shows the
linear performance of brute force. For a 0.23 ratio, the kd-tree implementation
only outperforms ford=2 andn≤8,192; however, for a ratio of 0.014375, the
kd-tree implementation wins ford≤6 andn≤131,072.
Table 9-7. Comparing Range Query execution times in milliseconds (kd-tree versus brute
force) for situation 1
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 51.4 73.9 94.3 124.5 10.5 13.0 12.7 13.6
8,192 199.6 204.3 215.6 228.8 17.8 20.8 25.4 26.0
16,384 354.3 375.1 401.7 422.9 33.7 44.4 55.7 66.1
32,768 678.5 765.8 780.7 827.0 90.8 116.3 129.9 145.3
65,536 1397.3 1482.2 1612.6 1817.8 189.7 226.6 266.4 315.0
131,072 2924.5 3146.4 3305.6 3738.9 378.3 458.9 534.5 638.9
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use