Nearly all major commercial computer-aided design systems have adopted a feature-based design approach to solid modeling. Models are created via a sequence of operations which apply design features to incremental versions of a design model. Even surfacing, free-form surface shaping, and deformation operations are internally represented in modeling systems as features in a "history tree" that generates the final design. Much in the same manner that Constructive Solid Geometry (CSG) trees for an individual model can be non-unique, these design feature histories for solid models might be ordered in a number of ways and still result in the same final geometry and topology.

We formulate this problem symbolically and present geometric reasoning techniques to generate a canonical form for certain classes of design feature histories. We define this representation as a Model Dependency Graph (MDG) and show how it can be used as a basis for developing techniques for managing databases of solid models. Using the MDG, we introduce algorithms that can assess the similarity of solid models based on design features. One of these algorithms computes an approximation to the subgraph isomorphism and graph isomorphism problems using a random restart gradient descent approach. Another of these algorithms uses the search method known as A* to detect subgraph isomorphism. We believe these techniques can be used to build intelligent CAD knowledge-bases and to identify meaningful part families from large sets of designs. Lastly, we describe experimental results and performance metrics for our approach.