Analyzing and dynamically indexing the query set

Abstract

Most of the current metric indexes focus on indexing the collection of reference. In this work we study the problem of indexing the query set by exploiting some property that query object smay have. There after, we present the Snake Table, which is an index structure designed for supporting streams of k-NN searches with in a content-based similarity search framework. The index is created and updated in the online phasewhile resolving the queries, thus it does not need a preprocessing step. This index is in tended to be used when the stream of query objects fitsa snake distribution, that is, when the distance between two consecutive query objects is small. In particular,this kind of distribution is present in content-based video retrieval systems, image class if ication based on local descriptors, rotation-invariant shape matching,and others. We show that the Snake Table improves the efficiency of k-NN searches in these systems, avoiding the building of as tatic index in the off line phase.