Minimal Cost Spanning Trees for Nearest-Neighbour Matching
Joselíto J. Chua, Peter Eric Tischer · 1999
A fundamental activity common to many image processing, pattern classification, and clustering algorithms involves searching a large set of high-dimensional data for the one which is nearest to a given target item with respect to a distance function. We propose the use of a minimal cost spanning tree (MCST) for an effective data structure in minimising the cost of the search. We present an algorithm which is full-search equivalent, and requires only O(n) space. Results indicate that the use of the MCST leads to fast and economical nearest-neighbour search algorithms comparable to many of the recently proposed techniques.