12/01/1994 09:00 AM
Computer Science
Major applications of graph-based knowledge representations will require quick response times on extremely large knowledge bases. Although algorithmic developments have provided tremendous improvements in speed, we believe implementation on parallel processors will be needed to meet long-term needs. This paper presents a new parallelization of a subgraph isomorphism refinement algorithm for performing projection tests and retrieving conceptual structures. The improved algorithm is faster, requires fewer processors, and is compatible with recent relation-based representations of conceptual structures. The new parallelization takes advantage of the features of contemporary data-parallel parallel machines by exploiting bit- parallelism in wide data words. Processing numerous graphs on a single parallel array, it combines the strengths of prior parallel subgraph isomorphism implementations with multi-level indexed search. It incorporates lattice codes of the concept-type hierarchy to avoid a bottleneck in our prior parallelization and forms all node candidate binding lists in parallel. Simulation results of the behavior of the refinement algorithm with parameterized synthetic data sets are presented as are implications for hardware tailored to processing conceptual structures.
