Test of Closest Pair Data Structures

Hierarchical Clustering in R20

Brute Force Neighbors Quadtree Conga Line MultiConga FastPair
n = 250 5.76s 0.60s 0.36s 1.09s 0.38s 0.36s
500 53.80s 2.48s 1.71s 5.98s 1.65s 1.52s
1000 456.98s 10.24s 7.94s 28.17s 7.10s 6.75s
2000 4145.91s 46.41s   154.25s 35.35s 31.88s
4000   204.14s   785.14s 165.58s 148.76s
8000   841.34s   3644.60s 747.80s 659.85s
16000   3337.03s     3051.22s 2709.94s

Clusters are combined by unweighted medians. Points were placed uniformly at random in the unit hypercube.Times include only the construction of the closest pair data structure and algorithm execution (not the initial point placement) and 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).