Efficient Search with Changing Similarity Measures on Large Multimedia Datasets

Abstract

In this paper, we consider the problem of finding the k most simi- lar objects given a query object, in large multimedia datasets. We focus on sce- narios where the similarity measure itself is not fixed, but is continuously being refined with user feedback. Conventional database techniques for efficient simi- larity search are not effective in this environment as they take a specific similar- ity/distance measure as input and build index structures tuned for that measure. Our approach works effectively in this environment as validated by the experimental study where we evaluate it over a wide range of datasets. The experiments show it to be efficient and scalable. In fact, on all our datasets, the response times were within a few seconds, making our approach suitable for interactive applications.