Test of Closest Pair Data Structures

Greedy Matching with Random Distances

Brute Force Neighbors Quadtree Conga Line MultiConga FastPair
n = 250 2.73s 0.16s 0.19s 0.25s 0.12s 0.12s
500 21.76s 0.65s 0.90s 1.29s 0.50s 0.46s
1000 173.91s 2.64s 4.18s 6.20s 2.03s 1.89s
2000 1402.60s 10.80s   28.94s 8.45s 7.72s
4000   44.43s   167.86s 34.87s 31.97s
8000   179.94s   598.28s 142.23s 131.21s
16000   762.80s   2818.09s 600.74s 556.67s
32000   3130.31s     2485.36s 2223.75s

Greedy matching was performed on distance matrices constructed at random. Distances were computed on the fly by using indices as seeds to a random number generator, so the matrix did not need to be stored in core. Times are averages over ten runs. The quadtree data structure was only run on data sets of 1000 or fewer points due to its high storage requirements. Code was written in C++, compiled and optimized by Metrowerks Codewarrior 10, and run on a 200MHz PowerPC 603e processor (Apple Powerbook 3400c).