Fast nearest-neighbor search algorithms based on approximation-eliminationsearch

In this paper, we provide an overview of fast nearest-neighbor search algor ithms based on an 'approximation-elimination' framework under a class of el imination rules, namely, partial distance elimination, hypercube eliminatio n and absolute-error-inequality elimination derived from approximations of Euclidean distance. Previous algorithms based on these elimination rules ar e reviewed in the context of approximation-elimination search. The main emp hasis in this paper is a comparative study of these elimination constraints with reference to their approximation-elimination efficiency set within di fferent approximation schemes. (C) 2000 Pattern Recognition Society. Publis hed by Elsevier Science Ltd. All rights reserved.