Database techniques for archival of solid models

ABSTRACT

This paper presents techniques for managing solid models in modern relational database management systems. Our goal is to enable support for traditional database operations (sorting, distance metrics, range queries, nearest neighbors, etc) on large databases of solid models. As part of this research, we have developed a number of novel storage and retrieval strategies that extend the state-of-the-art in database research as well as change the way in which solid modeling software developers and design and manufacturing enterprises view CAD-centric data management problems.

Past research and current commercial systems for engineering information management and Product Data Management (PDM) have predominantly taken annotation and document-based approaches—where the solid modeling data itself is simply stored as a related file to other project documents. Research in CAD and engineering databases has produced great advances, such as representation schemas for STEP-based data elements, however existing technologies stop short of enabling content-based and semantic retrieval of solid modeling data of the types now available for other higher-dimensional media (images, audio and video).

Our approach encodes solid model BRep information as a Model Signature Graph. We demonstrate how Model Signature Graphs can be used for topological similarity assessment of solid models and enable clustering for data mining of a large design repositories. We believe this work will begin to bridge the solid modeling and database communities, enabling new paradigms for interrogation of CAD datasets.

REFERENCES

• 1: National design repository. http : //www. designrepository, org., 2000.
• 2: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 3: Norman L. Biggs. Algebraic Graph Theory. Cambridge Tracts in Mathematics 67. Cambridge University Press, 1974.
• 4: Tolga Bozkaya , Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.357-368, May 11-15, 1997, Tucson, Arizona, United States
• 5: Sergey Brin, Near Neighbor Search in Large Metric Spaces, Proceedings of the 21th International Conference on Very Large Data Bases, p.574-584, September 11-15, 1995
• 6: H. Bunke, On a relation between graph edit distance and maximum common subgraph, Pattern Recognition Letters, v.18 n.9, p.689-694, Aug. 1997 [doi>10.1016/S0167-8655(97)00060-3]
• 7: Fan R. K. Chung. Spectral Graph Theory. Number 92 in Regional Conference Series in Mathematics. American Mathematical Society, 1997.
• 8: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 9: Kurt D. Cohen. Feature extraction and pattern analysis of three-dimensional objects. Master's thesis, Dartmouth College, Thayer School of Engineering, Hanover, NH, 1996.
• 10: George Cybenko, Aditya Bhasin, and Kurt D. Cohen. 3d base: An agent-based 3d object recognition system, http://compeng-www.dartmouth.edu/3d, January 1996.
• 11: George Cybenko, Aditya Bhasin, and Kurt D. Cohen. Pattern recognition of 3d cad objects: Towards an electronic yellow pages of mechanical parts. Technical report, Dartmouth College, Thayer School of Engineering, Hanover, NH, January 1996.
• 12: M. Ester, H.P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings 2nd International Conference on Knowledge Discovery and Data Mining (KDD'96), pages 226--231, 1996.
• 13: Daniel Fasulo. An analysis of recent work on clustering algorithms. Web??, April 1999. http://citeseer.nj.nec.com/fasulo99analysi.html.
• 14: Miroslav Fiedler. Eigenvectors of acyclic matrices. Czechoslovak Mathematical Journal, 25:607--618.
• 15: Miroslav Fiedler. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23:298-305, 1973.
• 16: Miroslav Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical,lournal, 25:619-633, 1975.
• 17: Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293- 306, 1985.
• 18: Amarnath Gupta , Ramesh Jain, Visual information retrieval, Communications of the ACM, v.40 n.5, p.70-79, May 1997 [doi>10.1145/253769.253798]
• 19: M. Hardwick, K.C. Morris, D. L. Spooner, T. Rando, and P. Denno. Lessons learned developing protocols for the industrial virtual enterprise. International Journal of Computer Aided Design, 32(2): 159-166, Februrary 2000.
• 20: Martin Hardwick , David L. Spooner , Tom Rando , K. C. Morris, Sharing manufacturing information in virtual enterprises, Communications of the ACM, v.39 n.2, p.46-54, Feb. 1996 [doi>10.1145/230798.230803]
• 21: Martin Hardwick , K. C. Morris , David L. Spooner , Thomas Rando, Data Protocols for the Industrial Virtual Enterprise, IEEE Internet Computing, v.1 n.1, p.20-29, January 1997 [doi>10.1109/4236.585169]
• 22: Bruce Hendrickson , Robert Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, SIAM Journal on Scientific Computing, v.16 n.2, p.452-469, March 1995 [doi>10.1137/0916028]
• 23: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 24: Anil K. Jain , Richard C. Dubes, Algorithms for clustering data, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 25: S. Joshi , T. C. Chang, Graph-based heuristics for recognition of machined features from a 3D solid model, Computer-Aided Design, v.20 n.2, p.58-66, March, 1988 [doi>10.1016/0010-4485(88)90050-4]
• 26: Leonard Kaufman and Peter J. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis. John Wiley and Sons, Inc., 1990.
• 27: J. MacQueen. Some methods for classification and analysis of multivariate observations. In Proceedings of 5th Berkeley Symposium, pages 281-297, 1967.
• 28: M. Otterman. Approximate matching with high dimensionality R-trees. M.Sc Scholarly paper, Dept of Computer Science, Univ. of Maryland, Collage Park, MD, 1992.
• 29: William C. Regli and Daniel M. Gaines. A national repository for design and process planning. In National Science Foundation Design and Manufacturing Grantees Conference, pages 673-674, Seattle, Washington. January 7- l 0., 1997.
• 30: William C. Regli and Daniel M. Gaines. An overview of the NIST Repository for Design, Process Planning, and Assembly. International Journal of Computer Aided Design, 29(12):895-905, December 1997.
• 31: Ali Shokoufandeh, Sven J. Dickinson, Kaleem Siddiqi, and Steven W. Zucker. Indexing using a spectral encoding of topological structure. Computer Vision and Pattern Recognition, 2, 1999.
• 32: David L. Spooner , Martin Hardwick, Using Views for Product Data Exchange, IEEE Computer Graphics and Applications, v.17 n.5, p.58-65, September 1997 [doi>10.1109/38.610208]
• 33: Tien-Lung Sun, Chuan-Jun Su, Richard J. Mayer, and Richard A. Wysk. Shape similarity assessment of mechanical parts based on solid models. In Rajit Gadh, editor, ASME Design for Manufacturing Conference, Symposium on Computer Integrated Concurrent Design, pages 953-962. ASME, Boston, MA. September 17-21.1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

General Terms:
Design, Experimentation, Management, Measurement, Performance, Theory

Keywords:
database clustering, database indexing, geometric reasoning, shape similarity, solid modeling