PATTERN ASSOCIATIVITY AND THE RETRIEVAL OF SEMANTIC NETWORKS

Four methods for the associative retrieval of semantic networks are described. These methods differ from those traditional approaches, such as SNEPS, in which an entire knowledge base is treated as a single network. Here the knowledge base is viewed as an organized collection of networks and is most appropriate for applications (such as bibliographic retrieval) in which pieces of knowledge need to be treated individually. Method I is an arbitrary flat ordering of database graphs, Method II a two-level ordering, and Method III is a full partial order. Method IV is a novel method known as "hierarchical node descriptor method" that is based on the "refinement" method of subgraph-isomorphism. A "pattern associativity" principle explains the development and effectiveness of each of these methods. Moving from Method I through Method IV there is a steady increase in both pattern associativity and efficiency. A theorem is proven that establishes the superiority of Method III over Method II despite the fact that Method II is the method most often used. A brief discussion of how parallelism may be incorporated also accompanies the description of each method. Most of the paper applies these methods to conceptual graphs and a later section shows how the techniques can be extended to other semantic-network formalisms. The paper concludes by showing how generalization graphs constructed through pattern associativity may also have semantic validity in the domains from which they have been derived.