Digital Symposium Collection 2000

Efficient Geometry-based Similarity Search of 3D Spatial Databases Daniel A. Keim   View Paper (PDF)   Return to Similarity Search Abstract Searching a database of 3D-volume objects for objects which are similar to a given 3D search object is an important problem which arises in number of database applications - for example, in Medicine and CAD. In this paper, we present a new geometry-based solution to the problem of searching for similar 3D-volume objects. The problem is motivated from a real application in the medical domain where volume similarity is used as a basis for surgery decisions. Our solution for an efficient similarity search on large databases of 3D volume objects is based on a new geometric index structure. The basic idea of our new approach is to use the concept of hierarchical approximations of the 3D objects to speed up the search process. We formally show the cor-rectness of our new approach and introduce two instantiations of our general idea, which are based on cuboid and octree approximations. We finally provide a performance evaluation of our new index structure revealing significant performance improvements over existing approaches. References Note: References link to DBLP on the Web. [ABKS 98] Mihael Ankerst , Bernhard Braunmüller , Hans-Peter Kriegel , Thomas Seidl : Improving Adaptable Similarity Query Processing by Using Approximations. VLDB 1998 : 206-217 [BKS 93] Thomas Brinkhoff , Hans-Peter Kriegel , Ralf Schneider : Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems. ICDE 1993 : 40-49 [BKSS 90] Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger : The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990 : 322-331 [BM 72] Rudolf Bayer , Edward M. McCreight : Organization and Maintenance of Large Ordered Indices. Acta Informatica 1 : 173-189(1972) [Fal 94] Christos Faloutsos , Ron Barber , Myron Flickner , Jim Hafner , Wayne Niblack , Dragutin Petkovic , William Equitz : Efficient and Effective Querying by Image Content. JIIS 3(3/4) : 231-262(1994) [Gut 84] Antonin Guttman : R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984 : 47-57 [Kei 97] ... [Kor 96] Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas : Fast Nearest Neighbor Search in Medical Image Databases. VLDB 1996 : 215-226 [MG 93] Rajiv Mehrotra , James E. Gary : Feature-Based Retrieval of Similar Shapes. ICDE 1993 : 108-115 [NLH 88] ... [Sam 90a] ... [Sam90b] Hanan Samet : The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990 [SFA 90] ... [SRF 87] Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos : The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987 : 507-518 BIBTEX @inproceedings{DBLP:conf/sigmod/Keim99,   author    = {Daniel A. Keim},    editor    = {Alex Delis and                 Christos Faloutsos and                 Shahram Ghandeharizadeh},    title     = {Efficient Geometry-based Similarity Search of 3D Spatial Databases},    booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference                 on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,                 USA},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-084-8},    pages     = {419-430},    crossref  = {DBLP:conf/sigmod/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM