Efficient User-Adaptable Similarity Search in Large Multimedia Databases

Efficient user-adaptable similarity search more and more increases in its importance for multimedia and spatial database systems. As a general similarity model for multi-dimensional vectors that is adaptable to application requirements and user preferences, we use quadratic form distance functions which have been successfully applied to color histograms in image databases [Fal+ 94]. The components aij of the matrix A denote similarity of the components i and j of the vectors. Beyond the Euclidean distance which produces spherical query ranges, the similarity distance defines a new query type, the ellipsoid query. We present new algorithms to efficiently support ellipsoid query processing for various user-defined similarity matrices on existing precomputed indexes. By adapting techniques for reducing the dimensionality and employing a multi-step query processing architecture, the method is extended to high-dimensional data spaces. In particular, from our algorithm to reduce the s imilarity matrix, we obtain the greatest lowerbounding similarity function thus guaranteeing no false drops. We implemented our algorithms in C++ and tested them on an image database containing 12,000 color histograms. The experiments demonstrate the flexibility of our method in conjunction with a high selectivity and efficiency.

Authors: Seidl T., Kriegel H.-P.
Published in: Proc. 23rd Int. Conf. on Very Large Data Bases (VLDB 1997), Athens, Greece
Publisher: Morgan Kaufmann
Sprache: EN
Jahr: 1997
Seiten: 506-515
ISBN: 1-55860-470-7
Konferenz: VLDB
Typ: Tagungsbeiträge
Forschungsgebiet: Exploration of Multimedia Databases