Utilization of principle axis analysis for fast nearest neighbor searches in high-dimensional image databases

Abstract

This paper presents an efficient indexing method for similarity searches in high-dimensional image database by principal axis analysis. linage databases often represent the image objects as high-dimensional feature vectors and access them via the feature vectors and similarity measure. However, the performance of the existing nearest neighbor search methods is far from satisfactory for feature vectors of large dimensions. An interesting approach to solve the problem is to conduct the similarity search by a filtering mechanism, which represents vectors as compact approximations and skips a large amount of irrelevant matches by first scanning these smaller approximations. In this paper, we introduce the principal axis analysis for constructing a high-dimensional projection line and the projection scores on the line for the vectors in the database are used as the approximations for filtering. We also pay attention to enhance the discriminatory power of the approximations by incorporating the projection scores on multiple principal axes which are orthogonal with each other. Experimental results demonstrate that the performance of proposed indexing scheme is superior to both of the LPC-file method [2] and the sequential scan in terms of elapsed time and the number of disk accesses.