Optimal incremental multi-step nearest-neighbor search
Ming Zhang, Reda Alhajj, Jon George Rokne · 2008
The distance measures used to determine the dissimilarities between high-dimensional feature vectors are often expensive to compute. To reduce the number of expensive distance calculations in the search process, Korn, et al [5] proposed a multi-step algorithm, which involves two stages: filtering and refinement. This algorithm was later improved by Seidl and Kriegel [8] to produce optimal-sized candidate set in the filtering stage; the improved algorithm is said to be filtering optimal, but can not produce the result incrementally in the refinement stage. In this paper, we propose an extended version of the algorithm that can produce the nearest neighbors incrementally in an optimal way. Our algorithm is both filtering and refinement optimal, and well serves real applications. We proved the optimality of the proposed extended algorithm.