A Framework for the Construction of Fast Nearest-Neighbour Search Algorithms

We propose a framework for fast nearest-neighbour (NN) search algorithms. The framework addresses the three main aspects of the NN search problem in high-dimensional space, namely: (i) how to star the search (ii) how to know when the search can terminate, and (iii) how to proceed with the search. We consider various solutions to these three aspects of the problem, and demonstrate how the framework can be used to find an NN search algorithm that can be suited to the resources and limitations of a given problem domain. We also propose using a partial ordering based on the minimum-cost spanning tree to determine how to proceed with the search. We present experimental results in vector quantisation (VQ) coding of images. Our results show that the framework can allow us to find a full-search equivalent solution efficiently while requiring only O(n) pre-computed information.