Abstract

Determining an efficient nearest-neighbour search technique is an important problem in many application areas which involve large collections of high-dimensional data. Data warehouses and multimedia databases, for example, require efficient methods for finding the closest match to a given query item with respect to a distance function. In this paper, we propose a nearest-neighbour search algorithm which uses a data structure based on the minimal cost spanning tree (MCST). The algorithm is full-search equivalent, and it requires only O(n) space for pre-computed information. Although the performance of the algorithm has not yet been verified analytically, our experiments on vector quantisation coding of images suggest that the use of the data structure leads to algorithms which can often find a nearest-neighbour in O(log n) distance function calculations. The results on our test data are comparable to many of the techniques proposed recently.