Algorithms in a Nutshell

(^290) | Chapter 9: Computational Geometry
The results in Figure 9-23 confirm that as the number of dimensions increases, the
benefit of using NEARESTNEIGHBORover brute force decreases. The cost of
constructing the kd-trees is not a driving factor in the equation, since that is
driven primarily by the number of data points to be inserted into the kd-tree, not
by the number of dimensions. On larger data set sizes, the savings is more
pronounced. Another reason for the worsening performance asdincreases is that
computing the Euclidean distance between twod-dimensional points is an O(d)
operation: asd increases, each computation simply takes more time.
Figure 9-22. Number of double recursions as n and d increase
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