SVD-Based Hierarchical Algorithm for Similarity Indexing in Quadratic Form Distance Space

摘要

Search based on content similarity in large multimedia library is essentially K-nearest neighbor search in high-dimensional feature spaces. In order to address the main issue influencing the real time property of similarity search for quadratic form distance -high dimension, this paper presents a hierarchical similarity indexing algorithm based on SVD (Singular Value Decomposition) technology, which first does considerably cheap approximate searching in the most significant subspace determined by SVD of the similarity matrix for quadratic form distance function based on similarity indexing structure, and then does linear exact searching in the full high-dimensional feature space on the results filtering through the first step. Experiments on a large (size> 10,000) indexable image database demonstrate the effectiveness and efficiency of our approach even in high dimensions such as 512 and 256.