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 d_A~2(x, y) = (x - y)· A · (x - y)~T which have been successfully applied to color histograms in image databases [Fal+ 94]. The components a_(ij) 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 similarity matrix, we obtain the greatest lower-bounding 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.