Nearly all major commercial computer-aided design systems have adopted a featurebased design approach to solid modeling. Models are created via a sequence of operations that apply design features to incremental versions of a design model. Even surfacing, freeform 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 nonunique, 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. Manufacturing features, easily obtained from the use of a feature recognition system, often map simply to manufacturing operations such as milling operations for some machine tool.

This problem is formulated symbolically and geometric reasoning techniques are presented to generate a representation of features and feature dependencies that deals with the non-uniqueness problem encountered in design feature histories. It is shown that this representation is not limited to design features and can be used with manufacturing features as well. The representation defined is termed the Model Dependency Graph (MDG) and alternatively the Undirected Model Dependency Graph (UMDG) and is used as a basis for developing techniques for managing databases of solid models. Using the MDG, algorithms are introduced that can assess the similarity of solid models based on design or manufacturing features and can be used in the retrieval of these models. 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. It is believed that these techniques can be used to build intelligent CAD knowledge bases and to identify meaningful part families from large sets of designs. Lastly, experimental results and performance metrics for these approaches are described. It is shown empirically that although the worst case complexity of solutions to the subgraph isomorphism problem is exponential the described algorithms’ performance on random graphs and on the UMDG is tractable in practice.