Inheritance Operations in Massively Parallel Knowledge Representation

This chapter elaborates on an approach to knowledge representation that combines the use of a limited inference strategy with massive parallelism. Conceptually, a class hierarchy is used. The nodes in this hierarchy are augmented by a preorder numbering scheme. The augmented hierarchy is then transformed into a pointer-free linear tree representation. This tree representation is implemented on a CM-2 Connection Machine, such that every node resides on its own processor. This chapter discusses in detail an algorithm for inheritance in the linear tree representation. It also introduces an algorithm for upward-inductive inheritance for the linear tree representation. Experimental data from a Connection Machine CM-2 implementation show that for a given machine size downward inheritance can be performed in constant time. The height of the class tree has no influence on the run time. Upward-inductive inheritance run times grow very moderately with the number of nodes in the tree.