Benchmarks

Static K-d Tree Benchmarks

For the following, point query structures were generated with randomly sampled 2D points, where each point lied in [0, 1] x [0, 1]. Benchmarks were performed using Bryan O'Sullivan's excellent criterion benchmarking library. Raw query times are reported, as well as speedups versus naive linear scans. Speedups are ratios between computation times of linear scan and k-d tree algorithms, with values < 1 representing slowdown.

building the k-d tree

\# Points | Times (ms)
______________________
 100      | 0.138
 1000     | 2.86
 10000    | 52.5
 100000   | 957

nearest neighbor

\# Points | Times (μs) | Speedup
________________________________
 100      | 1.7        | 0.42
 1000     | 2.3        | 3.2
 10000    | 3.1        | 23.5
 100000   | 3.6        | 262

k nearest neighbors

For all experiments, k = 10.

\# Points | Times (μs) | Speedup
________________________________
 100      | 9.4        | 0.78
 1000     | 12.2       | 2.5
 10000    | 14.2       | 16
 100000   | 17.3       | 138

all points within radius of query

For all experiments, radius = 0.05 (about ~0.8% of sampled volume for data points)

\# Points | Times (μs) | Speedup
________________________________
 100      | 1.7        | 0.77
 1000     | 5.3        | 2.5
 10000    | 25.2       | 5.2
 100000   | 240        | 6.0

all points within given range

For all experiments, specified range of size (0.1 x 0.1) centered on a random point in [0,1] x [0,1], or ~1% of the sampled volume for data points.

\# Points | Times (μs) | Speedup
________________________________
 100      | 2.2        | 2.1
 1000     | 6.4        | 6.9
 10000    | 31.5       | 13
 100000   | 385        | 11