article

Free access

Efficient geometry-based similarity search of 3D spatial databases

Author:

Daniel A. KeimAuthors Info & Claims

ACM SIGMOD Record, Volume 28, Issue 2

Pages 419 - 430

https://doi.org/10.1145/304181.304219

Published: 01 June 1999 Publication History

PDF eReader

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 correctness 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

[1]

Ankerst M., Bratmmtiller B., Kriegel H.-P., Seidl T.: Improving Adaptable Similarity Query Processing by Using Approximations, Proc. 24th Int. Conf. on Ver~ Large Data Bases, New York, 1998, pp. 206-217.

Digital Library

Google Scholar

[2]

BrinkhoffT., Kriegel H.-P., Schneider R.: 'Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems', Proc. 9th Int. Conf. on Data Engineering, Vienna, Austria, 1993, pp.40-49.

Digital Library

Google Scholar

[3]

Beckmann N., Kriegel H.-P., Schneider R., Seeger B." 'The R*-tree: An Efficient and Robust Access Method for Points and Rectangles', Proc. ACM SIG- MOD Int. Conf. on Management of Data, Atlantic City, NJ, 1990, pp. 322-331.

Digital Library

Google Scholar

[4]

Bayer R., McCreight E. M.: 'Organization and Maintenance of Large Ordered Indices', Acta informatica, Vol. 1, No. 3, pp. 173-189.

Google Scholar

[5]

Faloutsos C., Barber R., Flickner M., Hafner J., Niblack W., Petkovic D.: 'Efficient and Effective Querying by Image Content', Journal of Intelligent Informarion Systems, 1994, Vol. 3, pp. 231-262

Digital Library

Google Scholar

[6]

Guttman A.: 'R-trees: A Dynamic Index Structure for Spatial Searching', Proc. ACM SIGMOD Int. Conf. on Management of Data, Boston, MA, 1984., pp. 47-57.

Digital Library

Google Scholar

[7]

Keim D. A.: 'Efficient Support of Similarity Search in Spatial Data Bases', Habilitation thesis, University of Munich, 1997.

Google Scholar

[8]

Kom F., Sidiropoulos N., Faloutsos C., Siegel E., Protopapas Z.: 'Fast Nearest Neighbor Search in Medical Image Databases ', Proc. 22nd Int. Conf. on Very Large Data Bases, Mumbai, India, 1996, pp. 215-226.

Digital Library

Google Scholar

[9]

Mehrotra R., Gary J. E.: 'Feature-Based Retrieval of Similar Shapes', Proc. 9th Int. Conf. on Data Engineering, Vienna, Austria, 1993, pp. 108-115.

Digital Library

Google Scholar

[10]

Nborio H., Liang P., Hackwood S.: 'Construction of the Octree Approximating Three-Dimensional Objects Using Multiple Views', IEEE Trans. on Pattern Analysis and Machine Learning, Vol. 10, 1988, pp. 769-782.

Digital Library

Google Scholar

[11]

Samet H.: 'Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS', Addison-Wesley, 1990.

Digital Library

Google Scholar

[12]

Samet H.: 'The Design and Analysis of Spatial Data Structures', Addison- Wesley, 1990.

Digital Library

Google Scholar

[13]

Srinivasan P., Fukusa S., Azimoto S.: "Computational Geometric Methods in Volumetric Intersection for 3D Reconstruction', Pattern Recognition, Vol. 23, 1990, pp. 843-857.

Digital Library

Google Scholar

[14]

Sellis T., Roussopoulos N., Faloutsos C.: 'The R~-Tree: A Dynamic Index for Multi-Dimensional Objects', Proc. 13th Int. Conf. on Very Large Databases, Brighton, England, 1987, pp 507-518.

Digital Library

Google Scholar

Cited By

View all

Van den Herrewegen JTourwé Twyffels F(2024)Self-supervised learning for robust object retrieval without human annotationsComputers and Graphics10.1016/j.cag.2023.06.029115:C(13-24)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.cag.2023.06.029
Ghadai SLee XBalu ASarkar SKrishnamurthy A(2021)Multi-resolution 3D CNN for learning multi-scale spatial features in CAD modelsComputer Aided Geometric Design10.1016/j.cagd.2021.10203891:COnline publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.cagd.2021.102038
Orthuber W(2020)Information Is Selection—A Review of Basics Shows Substantial Potential for Improvement of Digital Information RepresentationInternational Journal of Environmental Research and Public Health10.3390/ijerph1708297517:8(2975)Online publication date: 24-Apr-2020
https://doi.org/10.3390/ijerph17082975
Show More Cited By

Index Terms

Efficient geometry-based similarity search of 3D spatial databases

Recommendations

Efficient geometry-based similarity search of 3D spatial databases
SIGMOD '99: Proceedings of the 1999 ACM SIGMOD international conference on Management of data

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 ...
Superseding Nearest Neighbor Search on Uncertain Spatial Databases

This paper proposes a new problem, called superseding nearest neighbor search, on uncertain spatial databases, where each object is described by a multidimensional probability density function. Given a query point q, an object is a nearest neighbor (NN) ...
Similarity search in fuzzy object databases
SSDBM '15: Proceedings of the 27th International Conference on Scientific and Statistical Database Management

Fuzzy object databases are becoming more and more important in the context of image analysis. Examples include satellite images where blurred trees, houses or lakes can still be organized and searched in a meaningful manner and biomedical images which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM SIGMOD Record Volume 28, Issue 2

June 1999

599 pages

ISSN:0163-5808

DOI:10.1145/304181

Chairmen:
Susan Davidson
Univ. of Pennsylvania
,
Christos Faloutsos
Carnegie Mellon Univ.

Issue’s Table of Contents

SIGMOD '99: Proceedings of the 1999 ACM SIGMOD international conference on Management of data
June 1999
604 pages
ISBN:1581130848
DOI:10.1145/304182
Chairmen:
Susan B. Davidson
Univ. of Pennsylvania, Philidelphia
,
Christos Faloutsos
Carnegie Mellon Univ., Pittsburgh

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1999

Published in SIGMOD Volume 28, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
1,009
Total Downloads

Downloads (Last 12 months)75
Downloads (Last 6 weeks)13

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Van den Herrewegen JTourwé Twyffels F(2024)Self-supervised learning for robust object retrieval without human annotationsComputers and Graphics10.1016/j.cag.2023.06.029115:C(13-24)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.cag.2023.06.029
Ghadai SLee XBalu ASarkar SKrishnamurthy A(2021)Multi-resolution 3D CNN for learning multi-scale spatial features in CAD modelsComputer Aided Geometric Design10.1016/j.cagd.2021.10203891:COnline publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1016/j.cagd.2021.102038
Orthuber W(2020)Information Is Selection—A Review of Basics Shows Substantial Potential for Improvement of Digital Information RepresentationInternational Journal of Environmental Research and Public Health10.3390/ijerph1708297517:8(2975)Online publication date: 24-Apr-2020
https://doi.org/10.3390/ijerph17082975
Bustos BSipiran I(2020)3D Shape Matching for Retrieval and Recognition3D Imaging, Analysis and Applications10.1007/978-3-030-44070-1_9(413-461)Online publication date: 12-Sep-2020
https://doi.org/10.1007/978-3-030-44070-1_9
Lara López GPeña Pérez Negrón AAntonio Jiménez ARamírez Rodríguez JImbert Paredes R(2017)Comparative analysis of shape descriptors for 3D objectsMultimedia Tools and Applications10.1007/s11042-016-3330-576:5(6993-7040)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s11042-016-3330-5
Lenz JDenner TLickefett MBauernhansl T(2015)Similarity-based Product Search for Next Generation Process PlanningProcedia CIRP10.1016/j.procir.2015.06.01233(59-63)Online publication date: 2015
https://doi.org/10.1016/j.procir.2015.06.012
Huang ZShen HZhou X(2008)Localized Co-Occurrence Model for Fast Approximate Search in 3D Structure DatabasesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2007.19072920:4(519-531)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1109/TKDE.2007.190729
Wong HMa BSha YIp H(2008)3D head model retrieval in kernel feature space using HSOMPattern Recognition10.1016/j.patcog.2007.06.00941:2(468-483)Online publication date: 1-Feb-2008
https://dl.acm.org/doi/10.1016/j.patcog.2007.06.009
Lu YKaneko KMakinouchi A(2007)Using a Partial Geometric Feature for Similarity Search of 3D ObjectsIPSJ Digital Courier10.2197/ipsjdc.3.6743(674-682)Online publication date: 2007
https://doi.org/10.2197/ipsjdc.3.674
Yubin YHui LYao Z(2007)Content-Based 3-D Model RetrievalIEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews10.1109/TSMCC.2007.90575637:6(1081-1098)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1109/TSMCC.2007.905756
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations