A pivot-based index structure for combination of feature vectors

Abstract

We present a novel indexing schema that provides efficient nearest-neighbor queries in multimedia databases consisting of objects described by multiple feature vectors. The benefits of the simultaneous usage of several (statically or dynamically) weighted feature vectors with respect to retrieval effectiveness have been previously demonstrated. Support for efficient multi-feature vector similarity queries is an open problem, as existing indexing methods do not support dynamically parameterized distance functions. We present a solution for this problem relying on a combination of several pivot-based metric indices. We define the index structure, present algorithms for performing nearest-neighbor queries on these structures, and demonstrate the feasibility by experiments conducted on two real-world image databases. The experimental results show a significant performance improvement over existing access methods.