Relevance Feedback in Large Multimedia Databases


Jelena Tesic, Peng Wu, B.S.Manjunath


It is in general impractical to store large amounts of extracted feature vectors in a random access memory (RAM). Since input/output (I/O) operations for hard storage devices are slow, the time spent accessing the feature vectors overwhelmingly dominates the time complexity of the search. In developing image/video search techniques, ``relevance feedback'' has been widely used in associating user's concept with the descriptors. During this learning process, the algorithm needs to access the descriptors associated with image/video objects. The time complexity problem is further exacerbated since the search is to be performed multiple times until user is satisfied with the retrieved results. So far, the impact of using learning on the indexing structure has generally been ignored. The feasibility of learning algorithms has not been evaluated for handling large amount of image/video data in relevance feedback scenarios. We believe that this is one of the first attempts to address the issue of efficient nearest neighbor search in relevance feedback in the literature.

The main contribution of this work is an efficient algorithm for repetitive searches to compute nearest neighbors in high dimensional feature spaces. This work addresses scenarios in which a similarity or distance matrix is updated during each iteration of the relevance feedback search, and a new set of nearest neighbors are computed. Nearest neighbor computation in each iteration is quadratic with number of dimensions and linear with number of items. The proposed scheme enables the use of the user's feedback not only to improve the effectiveness of the similarity retrieval, but also its efficiency in an interactive content based image retrieval system. It uses rectangular approximations for nearest neighbor search under quadratic distance metric and exploits correlations between two consecutive nearest neighbor sets. This adaptive approach significantly reduces the overall search complexity by reducing the number of assessed data on the hard storage devices up to 90 times.


These materials are presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each authors copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. Jelena Tesic, B.S. Manjunath, and Peng Wu, "Quadratic Distance Queries for Relevance Feedback," submitted to IEEE Transactions on Knowledge and Data Engineering, September 2003. J. Tesic and B.S. Manjunath, "Nearest Neighbor Search for Relevance Feedback," Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), Madison, Wisconsin, June 2003. [abstract] P. Wu, B.S. Manjunath, "Adaptive Nearest Neighbor Search for Relevance Feedback in Large Image Datasets," Proc. ACM International Multimedia Conference (MM '01), Ottawa, Canada, October 2001. [abstract]


This research was supported in part by The Institute of Scientific Computing Research (ISCR) award under the auspices of the U.S. Department of Energy by the Lawrence Livermore National Laboratory under contract No.W-7405- ENG-48, ONR# N00014-01-1-0391, NSF Instrumentation #EIA-9986057, and NSF Infrastructure #EIA-0080134.