3D Similarity Search by Shape Approximation

This paper presents a new method for similarity retrieval of 3D surface segments in spatial database systems as used in molecular biology, medical imaging, or CAD. We propose a similarity criterion and algorithm for 3D surface segments which is based on the approximation of segments by using multi-parametric functions. The method can be adjusted to individual requirements of specific applications by choosing appropriate surface functions as approximation models. For an efficient evaluation of similarity queries, we developed a filter function which supports fast searching based on spatial index structures and guarantees no false drops. The evaluation of the filter function requires a new query type with multidimensional ellipsoids as query regions. We present an algorithm to efficiently perform ellipsoid queries on the class of spatial index structures that manage their directory by rectilinear hyperrectangles, such as R-trees or X-trees. Our experiments show both, effectiveness as well as efficiency of our method using a sample application from molecular biology.

Authors: Kriegel H.-P., Schmidt T., Seidl T.
Published in: Proc. 5th Int. Symposium on Large Spatial Databases (SSD 1997), Berlin, Germany, LNCS 1262
Publisher: Springer - Heidelberg,Germany
Sprache: EN
Jahr: 1997
Seiten: 11-28
ISBN: 3-540-63238-7
Konferenz: SSD
Typ: Tagungsbeiträge
Forschungsgebiet: Exploration of Multimedia Databases