Test Data Sets

We tested the nearest-neighbor-lookup algorithm on several three-dimensional test data sets. For lack of a very large real data set, we created several artificial data sets by creating N 3D points uniformly randomly distributed in the 3D interval [-1, 1]3, and compared the performance on some of these random data sets to several surface point clouds downloaded from the Stanford 3D Scanning Repository. All data sets are represented by 3 32-bit floating-point numbers describing the coordinates for each point. The timing results for the artificial data sets are listed in Table 1; Table 2 contains the timings for the real data sets.
Data set sizeKd-tree Creation timePoint query timeKd-tree Creation time*Point query time*
100,00045.57 ms13.997 ms6.10 ms9.552 ms
200,00094.79 ms17.213 ms16.24 ms10.105 ms
427,645216.85 ms20.289 ms24.47 ms11.056 ms
500,000260.10 ms20.187 ms45.32 ms11.105 ms
533,652270.34 ms20.753 ms34.74 ms11.168 ms
1,000,000539.75 ms22.244 ms88.57 ms12.388 ms
2,000,0001,139.76 ms24.487 ms129.44 ms13.943 ms
3,599,6002208.38 ms25.700 ms239.27 ms14.897 ms
5,000,0003,108.70 ms26.766 ms334.09 ms15.548 ms
10,000,0006,670.60 ms29.118 ms688.19 ms16.767 ms
14,017,8729,610.97 ms29.756 ms1,014.51 ms17.386 ms
20,000,00013,617.00 ms30.769 ms1,417.79 ms18.120 ms
50,000,00036,289.70 ms33.340 ms3,782.70 ms19.586 ms
100,000,00074,792.70 ms35.694 ms7,538.09 ms21.344 ms
184,088,599143,047.00 ms41.705 ms14,559.00 ms22.306 ms
200,000,000158,897.00 ms42.690 ms15,649.60 ms22.616 ms
Table 1: Timing results for several artificial 3D data sets. All times are in milliseconds; the query times are the total times for performing 10,000 nearest-neighbor queries on randomly selected points from the source data set, removed before kd-tree creation. The data set sizes are the numbers of points after the 10,000 query points were removed. All times are wall-clock times, measured on a dual-CPU 2.2 GHz AMD Opteron with 8 GB of main memory (the algorithm is single-threaded and uses only one CPU). The starred times in the two rightmost columns are results from a newer computer, with a quad-core 2.67 GHz Intel i7 (Nehalem) CPU with 6 GB of main memory, using a new eight-way multithreaded kd-tree creation algorithm, and the same single-threaded query algorithm.
Data set nameData set sizeKd-tree Creation timePoint query time
Dragon427,645207.38 ms17.017 ms
Happy Buddha533,652274.80 ms18.488 ms
XYZ Dragon3,599,6001,867.39 ms27.631 ms
Lucy14,017,8728,125.88 ms24.784 ms
St. Matthew184,088,599(not available)(not available)
Table 2: Timing results for several real surface point cloud data sets downloaded from the Stanford 3D Scanning Repository. All times are in milliseconds; the query times are the total times for performing 10,000 nearest-neighbor queries on randomly selected points from the source data set, removed before kd-tree creation. The data set sizes are the numbers of points after the 10,000 query points were removed. All times are wall-clock times, measured on a dual-CPU 2.2 GHz AMD Opteron with 8 GB of main memory (the algorithm is single-threaded and uses only one CPU).
As seen from comparing identical-size data sets in Tables 1 and 2, the kd-tree creation times and query times differ only slightly between the artificial (uniform random) data sets and the real surface point cloud data sets; if at all, real data sets are processed slightly more efficiently. This leads us to believe that the algorithm scales well for real data sets as well, and that the preprocessing time/query time for the St. Matthew data set would be around 140 seconds/40 milliseconds, respectively.

Comparison to Other Methods

To evaluate the performance of our algorithm, we compared it against a recently announcend software package (Nearpt3) that uses a uniform grid data structure to speed up nearest-neighbor-lookup. The author of Nearpt3 claims that hierarchical data structures such as kd-trees are not well suited for NNL problems on very large data, as they are "so much larger that they cannot process the data sets used in [his] paper." The author also claims that the O(log N) query time makes them much slower than the O(1) query time associated with uniform grid methods (at least in the optimal case). Both these claims are obviously false; the zero memory overhead of the kd-tree structure described here is the optimal memory footprint to find nearest neighbors, as any method to solve the NNL problem must at least store all data points. The timing results from Tables 1 and 2 show that the query times might be asymptotically slower, but they beat the query times reported by the author of Nearpt3 by large factors even on his largest real-life data sets. On the St. Matthew data set (184,088,599 points), the author reports a preprocessing time of 128.71 seconds, which is slightly faster than our (estimated) time of 143 seconds, but a query time of 762 microseconds per query point, which is about 180 times slower than our (estimated) 4.17 microseconds per query. On a uniform random test data set containing 100 million points, the author reports a preprocessing time of 137 seconds and a query time of 47 microseconds; our method achieves a preprocessing time of 74 seconds, and a query time of 3.57 microseconds (one needs to keep in mind that uniformly randomly distributed points mark the optimal case for grid-based methods). Furthermore, the author represents all data sets as unsigned 16-bit integers for each component, which cuts the memory footprint (and bandwidth) in half but is not appropriate for accurate nearest-neighbor lookup.