Depth-first k-nearest neighbor finding using the MaxNearestDist estimator

Similarity searching is an important task when trying to find patterns in applications which involve mining different types of data such as images, video, time series, text documents, DNA sequences, etc. Similarity searching often reduces to finding the k nearest neighbors to a query object. A description is given of how to use an estimate of the maximum possible distance at which a nearest neighbor can be found to prune the search process in a depth-first branch-and-bound k-nearest neighbor finding algorithm. Using the MaxNearestDist estimator (Larsen, S. and Kanal, L.N., 1986) in the depth-first k-nearest neighbor algorithm provides a middle ground between a pure depth-first and a best-first k-nearest neighbor algorithm.