Adaptive Nearest Neighbor Search
for Relevance Feedback in Large Image Databases

P. Wu and B.S. Manjunath
Department of Electrical and Computer Engineering
University of California, Santa Barbara, CA 93106-9560
{peng, manj}@ece.ucsb.edu

Abstract

Relevance feedback is often used in refining similarity retriev-als
in image and video databases. Typically this involves modifi-cation
to the similarity metrics based on the user feedback and
recomputing a set of nearest neighbors using the modified similar-ity
values. Such nearest neighbor computations are expensive
given that typical image features, such as color and texture, are
represented in high dimensional spaces. Search complexity is a
critical issue while dealing with large databases and this issue has
not received much attention in relevance feedback research. Most
of the current methods report results on very small data sets, of
the order of few thousand items, where a sequential (and hence
exhaustive search) is practical. The main contribution of this
paper is a novel algorithm for adaptive nearest neighbor compu-tations
for high dimensional feature vectors and when the number
of items in the database is large. The proposed method exploits the
correlations between two consecutive nearest neighbor searches
when the underlying similarity metric is changing, and filters out
a significant number of candidates in a two stage search and
retrieval process, thus reducing the number of I/O accesses to the
database. Detailed experimental results are provided using a set
of about 700,000 images. Comparison to the existing method
shows an order of magnitude overall improvement.