Efficient KNN search by linear projection of image clusters

K‐nearest neighbors (KNN) search in a high‐dimensional vector space is an important paradigm for a variety of applications. Despite the continuous efforts in the past years, algorithms to find the exact KNN answer set at high dimensions are outperformed by a linear scan method. In this paper, we propose a technique to find the exact KNN image objects to a given query object. First, the proposed technique clusters the images using a self‐organizing map algorithm and then it projects the found clusters into points in a linear space based on the distances between each cluster and a selected reference point. These projected points are then organized in a simple, compact, and yet fast index structure called array‐index. Unlike most indexes that support KNN search, the array‐index requires a storage space that is linear in the number of projected points. The experiments show that the proposed technique is more efficient and robust to dimensionality as compared to other well‐known techniques because of its simplicity and compactness. © 2011 Wiley Periodicals, Inc.