Fast k-NN search using pre-computed l-NN sets

Abstract

The k-nearest neighbor (k-NN) query is to find the k nearest data points to a given query point. The speed of k-NN queries is very important for many spatial applications such as Geographic Information Systems (GIS). In many cases, spatial data stored in such systems do not change frequently, and this gives us an opportunity for speeding up k-NN queries. In this paper, we develop a method for speeding up k-NN queries using pre-computed l-nearest neighbor (l-NN) sets. Our method pre-computes and maintains the l nearest data points to each data point and exploits them to prune the search space for k-NN queries. To minimize the cost of reading l-NN sets from the disk, we also propose a method for determining the minimum value l' such that we can benefit from using l'-NN data points to process a given k-NN query. We prove that our method always returns the correct results and present the complete algorithms for processing k-NN queries and for maintaining l-NN sets. The experimental results show that our method significantly outperforms the conventional method.