Clique graph models for independent computations

A good solution to a computing problem that involves massive amounts of data depends heavily on the formulation of a good model of the structure of relationships among the data elements of the problem. If strongly related data can be grouped for similar processing, then the strong relationships should be apparent in the model. If weakly related data can be processed independently, then this also should be apparent in the model. One model that shows structural interrelationships clearly is the clique graph. Clique graphs are used in the development of divide-and-conquer algorithms, sparse matrix factorization schemes, and information propagation in knowledge-based systems, among other important applications.

This dissertation develops new results in clique graphs with emphasis on applications that involve independent processing. A new representation of clique graph structure based on clique intersections, called exclusive intersections, is introduced. Templates based on exclusive intersections that describe structural patterns in clique graphs are proposed. An important new method developed by Lauritzen and Spiegelhalter for handling uncertainty in knowledge-based systems uses a clique graph model to which these results are applicable. New results in this dissertation demonstrate how the amount of computation may be reduced and certain processes may be executed independently within the Lauritzen - Spiegelhalter method.