Efficient KNN search by linear projection of image clusters

✍ Scribed by Zaher Al Aghbari; Ayoub Al-Hamadi

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 415 KB
• Volume: 26
• Category: Article
• ISSN: 0884-8173
• DOI: 10.1002/int.20496

✦ Synopsis

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.