Improving Adaptable Similarity Query Processing by Using Approximations
Mihael Ankerst, Bernhard Braunmüller, Hans‐Peter Kriegel, Thomas Seidl · 1998
Similarity search and content-based retrieval are becoming more and more important for an increasing number of applications including multimedia, medical imaging, 3D molecular and CAD database systems. As a general similarity model that is particularly adaptable to user preferences and, therefore, fits the subjective character of similarity, quadratic form distance functions have been successfully employed, e.g. for color histograms as well as for 2D and 3D shape histograms. Although efficient algorithms for processing adaptable similarity queries using multidimensional index structures are available, the quadratic nature of the distance function strongly affects the CPU time which in turn represents a high percentage of the overall runtime. The basic idea of our approach is to reduce the number of exact distance computations by adapting conservative approximation techniques to similarity range query processing and, in addition, to extend the concepts to k-nearest neighbor search. As part of a detailed analysis, we show that our methods guarantee no false drops. Experiments