opening it up with Common Lisp
Book review: Darwinia
Summer reading: Spin
the Omnivoire's Delimma
the Golem's Eye
LAW: A Workbench for Approximate Pattern Matching in Relational Data
The Link Analysts Workbench (LAW) is an SRI developed tool designed to "assist the intelligence community in creating and maintaining patterns, matching those patterns against relational data and manipulating partial results." A LAW pattern includes a graph with typed vertexes and labeled edges. These graphs are built up out of a pattern language meant to be understandable to non computer-scientists but expressive enough to represent patterns of interest. Patterns also include a description of how near a match in the data needs to be (measured by graph edit distance) for it to be included in a query result set.
The graph edit distance metric used by LAW includes costs for each operation (node/edge changes, type changes, etc.). It includes an ontological distance based sub-typing (e.g., replacing a phone call with communication). It's not clear where the ontology comes from (those it's probably Cyc related) or what might happen if the analyst's ontology differs from that of the systems. Given the metric, LAW uses an A* search based anytime algorithm to find matches in the data set. These will be sub-graphs of the relational data set that are close to the pattern. They are presented to the analyst graphically so that it is clear exactly how the match was made.
LAW's architecture is web based. It uses XML to transmit pattern, hypothesis and control information and SOAP as an RPC mechanism. LAW is designed to handle multiple exploratory tools working in tandem (for example, different pattern matchers, group detection algorithms, etc.)
Extensions in the works are a more powerful pattern description language, scalability work, better semantic control and improved automation of multiple tasks -- sounds as if a blackboard architecture might be handy!
This is a well written application paper showing a variety of tools being used together to (partially) solve a difficult problem.
Copyright -- Gary Warren King, 2004 - 2006