ANN assumes that distances are measured using any class of distance functions called Minkowski metrics. These include the well known Euclidean distance, Manhattan distance, and max distance. Based on our own experience, ANN performs quite efficiently for point sets ranging in size from thousands to hundreds of thousands, and in dimensions as high as 20. The library also comes with test programs for measuring the quality of performance of ANN on any particular data sets, as well as programs for visualizing the structure of the geometric data structures. Computing exact nearest neighbors in dimensions much higher than 8 seems to be a very difficult task.
Few methods seem to be significantly better than a brute-force computation of all distances.
ANN allows the user to select a maximum error factor, thus providing a tradeoff between accuracy and running time. ANN can be downloaded by anonymous ftp from the University of Maryland. Back to Dave Mount's home page. Last updated on June 24, 1998.