Fast nearest-neighbor search algorithms based on approximation-elimination search

摘要

In this paper, we provide an overview of fast nearest-neighbor search algorithms based on an `approximation–elimination’ framework under a class of elimination rules, namely, partial distance elimination, hypercube elimination and absolute-error-inequality elimination derived from approximations of Euclidean distance. Previous algorithms based on these elimination rules are reviewed in the context of approximation–elimination search. The main emphasis in this paper is a comparative study of these elimination constraints with reference to their approximation–elimination efficiency set within different approximation schemes.