Optimal multi-step k-nearest neighbor search

For an increasing number of modern database applica-tions, efficient support of similarity search becomes an important task. Along with the complexity of the objects such as images, molecules and mechanical parts, also the complexity of the similarity models increases more and more. Whereas algorithms that are directly based on in-dexes work well for simple medium-dimensional similar-ity distance functions, they do not meet the efficiency re-quirements of complex high-dimensional and adaptable distance functions. The use of a multi-step query process-ing strategy is recommended in these cases, and our in-vestigations substantiate that the number of candidates which are produced in the filter step and exactly evalu-ated in the refinement step is a fundamental efficiency parameter. After revealing the strong performance shortcomings of the state-of-the-art algorithm for k-nearest neighbor search [Korn et al. 1996], we present a novel multi-step algorithm which is guaranteed to pro-duce the minimum number of candidates. Experimental evaluations demonstrate the significant performance gain over the previous solution, and we observed average improvement factors of up to 120 for the number of can-didates and up to 48 for the total runtime.