Similarity Search

Ludwig-Maximilians-Universität München
Institut für Informatik
Lehr- und Forschungseinheit für Datenbanksysteme

University of Munich
Institute for Computer Science
Database and Information Systems

[ Objective | Techniques | Applications & Demos | Publications | Team ]

Similarity Search in Spatial and Multimedia Databases

d_A²(o,q) = (o-q)·A·(o-q)^T

Objective

Development and investigation of new database techniques that efficiently support similarity search in large databases for a variety of applications from Medical Imaging, Molecular Biology, Spatial and Multimedia databases. The underlying similarity models are particularly flexible and adaptable to the requirements of the applications or to individual user preferences by using quadratic form distance functions.

Techniques

d_A²(o,q) = (o-q)·A·(o-q)^T	Quadratic Form Distance Functions Similarity models profit from the use of quadratic forms as distance functions. By specifying appropriate cross-similarity weights for the dimensions of the feature vectors to be the components of the similarity matrix, similarity distance functions are adapted to specific application requirements or user preferences.
	Ellipsoid Query Processing using Index Structures By quadratic form distance functions, so called Ellipsoid Queries are specified. Our algorithm for efficient ellipsoid query processing works on any multidimensional index structure whose directory is organized by rectilinear rectangles including R-trees, R*-trees, X-trees, and Quadtrees.
	Ellipsoid Query Processing using Approximations Some legacy systems may resist an integration of the ellipsoid query algorithm. We developed approximation techniques that support similarity range queries as well as k-nearest neighbor queries and incremental similarity ranking that use bounding spheres or minimum bounding rectilinear boxes.
	Reduction of Dimensionality Existing multidimensional index structures do not support ultra-high-dimensional spaces very well. Techniques for reducing the dimensionality of feature vectors are extended to ellipsoid queries. As a result, our algorithm produces the optimal lower-bounding ellipsoid distance function in the reduced space.
	Optimal Multi-Step k-Nearest Neighbor Search In case of very complex distance evaluations, filter-refinement architectures help to improve the performance of query processing. Whereas techniques to support range queries were already available, our method addresses the efficient evaluation of k-nearest neighbor queries in a multi-step algorithm. This optimal algorithm ensures that only the minimal number of expensive exact evaluations has to be performed in the refinement step.
	k-Nearest Neighbor Classification Whereas performance is a serious problem for many k-nn classifiers, our query processor efficiently supports this data mining technique.

Applications and Demos

(Demo on 112,000 images)	Color-Oriented Similarity Search in Multimedia Databases An adaptable similarity model based on color histograms and quadratic form distance functions supports similarity search in large color image databases.
(Demos on 10,000 clip arts)	2D Shape Similarity Search in Image Databases A pixel-based similarity model is used for the retrieval of similar images. The similarity distance function is able to consider small local shifts and displacements in order to handle errors of measurement.
(Demo on 5,000 proteins)	3D Shape Similarity Search in Biomolecular Databases From a 3D protein database, molecules that have a similar 3D shape are retrieved by using a similarity model based on 3D shape histograms. (see Molecular Bioinformatics)
	Similarity Search for 3D Surface Segments As a part of protein-protein docking prediction, we perform a similarity search on 3D surface segments. Parametric surface functions including paraboloids and trigonometric polynomials are used to approximate the surface segments.
(Demo on medical images) (Demo on tumor images)	Classification and Similarity Search of Medical Images Based on a large medical image database, a k-nearest neighbor classifier is developed that predicts the location where an X-ray image is taken from. To support the diagnosis of bone tumors, similar cases are retrieved from a database of X-ray images. (Cooperation with IBE Großhadern, Prof. Dr. med. Dipl.-Psych. Karl Überla, Dr. med. Dipl.-Inform. Martin Dugas)