Nearest Neighbor Search for Relevance Feedback

 

Dept. of Electrical and Computer Engineering
University of California at Santa Barbara
Santa Barbara, CA 93106
Email: {jelena,manj}@ece.ucsb.edu

Abstract

We introduce the problem of repetitive nearest neighbor
search in relevance feedback and propose an efficient
search scheme for high dimensional feature spaces. Relevance
feedback learning is a popular scheme used in con-tent
based image and video retrieval to support high-level
concept queries. This paper addresses those 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 is computed. This repetitive nearest
neighbor computation in high dimensional feature spaces is
expensive, particularly when the number of items in the data
set is large. In this context, we suggest a search algorithm
that supports relevance feedback for the general quadratic
distance metric. The scheme exploits correlations between
two consecutive nearest neighbor sets thus significantly reducing
the overall search complexity. Detailed experimental
results are provided using 60 dimensional texture feature
dataset.