Publication Details

The Role of Higher-Order Constructs in the Inexact Matching of Semantic Graphs

by Wolverton, M. and Thomere, J.

in Proceedings of the AAAI Workshop on Link Analysis

Abstract

Inexact pattern matching using semantic graphs has a wide-ranging use in AI systems, particularly in machine vision, case-based reasoning, and, recently, in intelligence analysis applications. While much previous work in the area has focused on matching simple flat graphs, there is increasing need for and use of complex graphical patterns with higher-order constructs—hierarchical graphs, cardinality constraints, disjunction, and others. This paper reports the results of an experimental analysis of higher-order constructs in graphical patterns and their effect on pattern matching efficiency. The study focuses on two aspects of these constructs—the impact of cardinality constraints on representational power and matching speed, and the benefit of caching hierarchical match results. The analysis shows that both mechanisms provide a significant speedup over conventional flat graph matching.

Electronic Copies

Adobe PDF

BibTeX

EndNote

Associated Projects

The Link Analysis Workbench The goal of this project is to develop the Link Analysis Workbench (LAW), a Web-accessible tool where analysts and machines collaboratively perform link analysis by defining hierarchical and temporal patterns, that include uncertain and qualitative elements, and by defining search strategies for pattern application, through a graphical user interface that supports direct graphical browsing and editing of patterns, search strategies, and summaries and details of resulting matches.

AIC Personnel

	Name	Title	E-mail
	Thomere, Jerome F	Computer Scientist
	Wolverton, Michael J	Senior Computer Scientist