opening it up with Common Lisp

Favorite weblogs

Lisp Related

Bill Clementson

Finding Lisp


Planet Lisp



Talking Points Memo

This Modern World

Working for Change

Other home


Recent Readings

Book review: Darwinia
Reviewed: Friday, August 11, 2006

Summer reading: Spin
Reviewed: Saturday, August 5, 2006

Reviewed: Tuesday, July 18, 2006

the Omnivoire's Delimma
Reviewed: Wednesday, July 12, 2006

the Golem's Eye
Reviewed: Wednesday, May 31, 2006


LAW: A Workbench for Approximate Pattern Matching in Relational Data
Michael Wolverton, Pauline Berry, Ian Harrison, John Lowrance, David Morley, Andres Rodriguez, Enrique Ruspini, Jerome Thomere, 2003
Thursday, June 3, 2004

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.

Home | About | Quotes | Recent | Archives

Copyright -- Gary Warren King, 2004 - 2006