GR/J99353

Concurrent Architectures for Heterogeneous Knowledge Manipulation Systems

Alan Wood

Summary

This project, funded as part of the EPSRC's Architectures for Integrated Knowledge Manipulation Systems ( AIKMS ) programme, had two principal goals:

In case-based reasoning systems a solution to a new problem is proposed by retrieving solutions to similar problems from a set of previously encountered problems and their solutions -- a case base.

Retrieval from case based systems is typically achieved by applying a similarity measure. Existing CBR systems typically use very simple similarity measures, for example a weighted count of the exactly matching features. An alternative approach is one in which a similarity measure determines a partial ordering of the cases, with the retrieval mechanism returning the maximal cases with respect to the ordering.

A major contribution of this project was to generalize to similarity metrics, which subsume similarity measures by returning values taken from some arbitrary lattice. Appropriate lattices include those defined on basic data values (Booleans, integers, floats), as well as structured types (tuples, lists, arrays etc.). In this way it was possible to generalize many previous definitions of similarity, dispensing with the need for special built-in operators by using a single set of definitions applicable to all metrics irrespective of the result lattice. Metrics on the domains of individual attributes can be imputed to whole tuples, and may be combined in various ways to give new metrics. These metrics can be applied to the case base to calculate the maxima.

Generic operations are abstractions which represent groups of primitive operation patterns. A generic operation is therefore similar to a macro which is instantiated with the component operations for a particular problem, or a framework to which those operations are attached.

There are, as yet, no formal methods for deriving generic operations or algorithmic skeletons, consequently the project approached the problem of identifying these operations by taking the lead from the strong results coming from the theoretical work, and use the formalism as a guide to identifying the important operation classes and structures.

In order to connect the operations identified by the theory with various implementation strategies in the concrete LINDA platform, we developed a LINDA Abstract Machine (in essence an operational semantics), called Liam. Liam is expressed in terms of the Chemical Abstract Machine which draws on the chemical reaction metaphor for describing coordinating concurrent processes.

In summary, the project's principal results were:

Further Details

The project's homepage contains more details of the research together with links to published and pending papers and technical reports.