Search and indexing of high-dimensional feature spaces for similarity retrieval

The rapid proliferation of multimedia data, in both consumer and professional applications, has necessitated the development of new techniques for efficient and effective management of such data. In recent years, the image processing and computer vision research has led to significant progress in feature extraction and data analysis. There has also been considerable work on high dimensional indexing within the database research. One of the main contributions of this thesis is to identify and address some of the challenges that are at the interface of visual analysis and database indexing. In particular, the high dimensionality of the visual descriptors for data access pose problems in indexing and search. This is often referred to as the curse of dimensionality. We propose two new techniques that address this issue. In the first one, we propose an efficient dimensionality reduction method that significantly reduces the descriptor dimensions while maintaining the overall search and retrieval effectiveness of the descriptor. This is based on a weighted multidimensional scaling algorithm. The second technique introduces an adaptive index structure for nearest neighbor searches in high dimensions that adapts to the data distribution. This adaptive method offers orders of magnitude improvement in search and retrieval compared to the existing state of the art methods. Finally, we extend these methods to interactive learning systems such as those using relevance feedback. In relevance feedback, both the query and the underlying similarity metric may change based on the user's response. Nearest neighbor searches in this context can be very expensive for large databases. We propose a new technique that constrains the search space for efficient nearest neighbor searches when the similarity metric is changing. Extensive experimental results on real texture and color images are presented to demonstrate the effectiveness of the proposed methods.