We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Approximation-Based Similarity Search for 3-D Surface Segments.
- Authors
Kriegel, Hans-Peter; Seidl, Thomas
- Abstract
The issue of finding similar 3-D surface segments arises in many recent applications of spatial database systems, such as molecular biology, medical imaging, CAD, and geographic information systems. Surface segments being similar in shape to a given query segment are to be retrieved from the database. The two main questions are how to define shape similarity and how to efficiently execute similarity search queries. We propose a new similarity model based on shape approximation by multi-parametric surface functions that are adaptable to specific application domains. We then define shape similarity of two 3-D surface segments in terms of their mutual approximation errors. Applying the multi-step query processing paradigm, we propose algorithms to efficiently support complex similarity search queries in large spatial databases. A new query type, called the ellipsoid query, is utilized in the filter step. Ellipsoid queries, being specified by quadratic forms, represent a general concept for similarity search. Our major contribution is the introduction of efficient algorithms to perform ellipsoid queries on multidimensional index structures. Experimental results on a large 3-D protein database containing 94,000 surface segments demonstrate the successful application and the high performance of our method.
- Subjects
GEOGRAPHIC information systems; COMPUTER-aided design; THREE-dimensional display systems; DATABASE management; MOLECULAR biology; MEDICAL technology; COMPUTER software
- Publication
GeoInformatica, 1998, Vol 2, Issue 2, p113
- ISSN
1384-6175
- Publication type
Article
- DOI
10.1023/A:1009760031965