FGP: A Virtual Machine for Acquiring Knowledge from Cases

1 Introduction

The knowledge acquisition bottleneck is still one of AI's major problems. It hM engendered commentary from senior AI practitioners for years, sparked the current revival of interest in machine learning, and is the pri­ mary motivation behind a multi-million dollar project to Msemble a ma.':lsive knowledge ba.':le (on the order of 10 8 facts) [Guha and Lenat, 1990]. In recent workshops, many researchers have come to the conclusion that the effective use of large databa.':les is our best hope to break through this bottleneck [Friesen and Golshani, 1989]. Our work is in this vein, and is an attempt to devise a domain-independent software architecture and related algorithms to extract knowledge from a large database of unstructured cases, a term we define below.

CMes are similar to feature-vector representations of data, but more general. They may be incomplete; in­ dividual ca.':les need to have values for only an arbitrary subset of the universe of features. Cases are not assigned to fixed categories. Rather any feature in the featureuniverse is a potential category; the program must be willing to direct its inference process at determining the probable value of any arbitrary feature for a particular case. We say probable because we make no Msumption about consistency of cases. Two cases may have identical values along every dimension but one.

We adopt this definition because these are the char­ acteristics observed in cases drawn from real-world do­ mains. The question we sought to address is whether the static feature information stored in ca.':les provides enough material to do useful inferencing and learning. The approach we choose is exemplar-based ( cf. [Porter et al., 1990]) and relies on the ca.':les themselves to drive the inference engine. Our goals are the following: The system should "reMon" on the bMis of specific cMes and groups of ca.':les, and should therefore be able to cite specific precedents (including precedents that are them­ selves incompletely understood), to modify its behavior on the ba.':lis of every new information-providing trans­ action, and to subsume the functions of a conventional information-retrieval system. It should be a viable learn­ ing system, equalling or surpMsing the accuracy of other purely data-driven approaches to cla.':lsification and pre­ diction problems, and do this while maintaining its avail­ ability as a real-time system. Unlike typical connection­ ist approaches, it should be designed to interact with a user as a case is described incrementally, or to generate line-by-line commentary on new cases. Most important, it should attempt to display not only "quantitative" but "qualitative" expertise. In our experimental definition, qualitative expertise requires (particularly on hard ca.':les, but these are the whole point) pursuing possibly pre­ mature hypotheses, offering (occasionally brMh) guesses and citing interesting precedents on the basis of a small but evocative degree of feature overlap. We are develop­ ing "simulated speculation" in an effort to approximate this behavior.

2 The FGP machine

The program we've built in an initial attempt to real­ ize these properties is the FGP machine, after its bMic operations-fetch, generalize and project. We imagine the FGP machine's database as a collection of regions in space ( cf. the standard vector space text-retrieval model). Each element of the databa.':le corresponds to some region. Nearby regions correspond to nearby cases. When presented with an inquiry, the machine's basic task is to add to the database a new region correspond­ ing to the inquiry. Stationing itself on top of this new region (so to speak), the machine then looks around and reports the identities of the nearby regions-these will correspond to elements of the database that are nearby to, in other words closely related to, the subject of the inquiry. We can then inspect this list of nearby regions and "generalize" -determine which attributes tend to be shared in common by all or by most of them. We can guess that these common attributes are likely to hold true for the case being described in the inquiry as well.

Having reached whatever conclusions seem reasonable the machine simulates "speculation." Temporarily turn~ ing aside from the inquiry in hand, it focusses on any "evocative possiblities" that may have suggested them­ selves during the examination of nearby regions. An "evocative possibility" is a datum that might be true, and that would be significant if it were. The machine's interaction with the user (see Figure 1) represents a combination of fairly safe conclusions, speculation ex­ periments and the subsequent investigation of resulting guesses.

The system can operate interactively, but here it is working in "commentary" mode: the user presents an entire case; the system scans it element-by-element of­ fering comments. This case initially seems malig~ant (note the early mention of related cases with diagnoses of infiltrating ductal carcinoma); the fact that the mass has not changed in density and has no comet (contradict­ ing the system's guesses, which in the nature of guesses will often be wrong) points in the other direction ("cyst" and ."fed" refer to benign diagnoses); but further data, particularly the absence of a halo, tips the balance, and the system guesses that this is a malignant mass. This guess is correct, and the diagnosis was in fact infiltrating ductal carcinoma. This transcript is driven by a small collection of 67 cases, which is the only domain knowl­ edge provided.

An FG P machine is defined in terms of a single kind of data-object and three primitive operators. These de­ fine a virtual machine in terms of which the system is programmed. We summarize the essential points in the rem~inder of this section; see [Fertig and Gelernter, 1989; Fert1g, 1990] for further discussion.

2.1 Data-objects and databases

FG P machines run off a database of a single type of data­ object, a feature tuple to which we refer generically as a r. A .r consists basically of a list of attribute-value pairs; we g1ve examples below. An FGP database consists of an unordered collection of r's. A new case for inclusion in the database is presented as a T, and a query is an incomplete r-a partial list of attribute-value pairs, with a request that the system fill in certain missing ones.

Individual cases are stored in r's; paradigm cases (cases that represent not a single object or incident, but a generalized or prototypical object or incident) are stored in formally-equivalent "heavy r's", as we discuss. The basic FGP-operations described below operate on r's in-

dividually and in groups. The feature tuple ((name apple) (type fruit) (color red)) is a T that represents a single apple; ((name apple 100) (type fruit 100) (color (red 50) (yellow 50)))

is a T that represents one hundred different apples; half were yellow and half were red, and beyond this fact no individual apple can be distinguished. When the count field is omitted, "1" is the default . A relatively "weight­ ier" Tis aT that reflects a greater number of individual cases. We use M to represent an unordered collection of r's; an FGP database of stored cases and paradigms is an M. Cis a list of r's ordered on their "closeness" to some other r: we explain below.

2.2 Primitive operators

The three basic FGP operations are fetch, generalize and project. They work as follows .

fetch maps a T and an M to an £: given a feature­ tuple and a database of feature-tuples, it produces an ordered list of those feature-tuples in the database that are "closest to" the T mentioned in the query. fet ch uses a two-step procedure.

First it calculates a "distance" from the new point to every point in memory 1 ; all cases further away than some parameterized threshold are removed from further con­ sideration. The distance of one case from another cannot be statically determined; two cases may be more closely related in the context of one goal than in another. There­ fore fetch's calculation not only takes into consideration the number of shared attributes and their types, but also, in the context of a request to fill in values for missing attributes, the "evocativeness" of each with respect to the current goal-a more evocative feature is one that recalls a group of cases with a more highly focussed set of values for the goal attribute. 2 Features are weighted in the distance calculation in proportion to their evoca­ tiveness. The final distance score is the weighted sum of the individual feature distances normalized by the size (number of features) of the cases. In standard terms, the similarity metric measures the weighted euclidean distance between cases, where the weighting is done au­ tomatically and reflects the evocativeness of individual features with respect to the goal. The system comes with default feature distance metrics defined for nomi­ nal, ordinal, and dimensional (real-number valued) data, although user-defined feature metrics can be used to re­ flect more specialized knowledge of the domain.

Next fetch checks to see if there exists a well-defined group of very-close points among those remaining by per­ forming a crude cluster analysis. Details can be found in

1 This calculation needn't require that every r in M be examined; as a first cut, we can ignore all cases that fail to intersect the query on at least one attribute. We use hashing to determine the candidate cases (to exclude the irrelevant ones).

2 The evocativeness of an attribute-value pair with respect to a goal attribute is inversely proportional to the entropy (disorder) of the distribution of values for the goal repre­ sented in the group of cases returned by fetch.

(AGE 58) (MASS..DENSITY ISO..DENSE) (MASS...BORDEILCOMPLETE? NO) (MASS_TYPE...BORDER IRREGULAR) (MASS...BORDER..DEFINED? NO) (MASS-LOCATION UIL) (MASS....SIZE_CHANGED? YES) (MASS..DENSITY_CHANGED? NO) (MASS_CQMET? NO) (MASS...HALO? NO) (BACKGROUND..DENSITY MODERATE) (SKIN_CHANGES HO) (NIPPLEJNVERSIOH? HO) (ADENOPATHY? NO) (FAMILY...HISTORY_CAHCER SISTER) (PERSONAL...HISTORY_CAHCER HO) Speculating: MASS_DENSITY_CHANGED? ... Guessing INCREASED - e.g. case ((id 14) (age 46) (diagnosis CAJNF..DUCTAL)) case ((id 50) (age 70) (diagnosis CAJNF..DUCTAL)) Speculating: MASS_COMET? ... Guessing YES - e.g. case 14 case ((id 40) (age 69) (diagnosis CAJNF..DUCTAL)) Speculating: BACKGROUND_DENSITY ... Guessing DENSE - e.g. case ((id 21) (age 61) (diagnosis cyst)) case ((id 47) (age 45) (diagnosis fed)) Concluding (ARCHITECTURAL-DISTORTION? NO) Speculating: MALIGNANT? ... Guessing YES- e.g. cases (2 6 8) Speculating: SKIN_CHANGES ... Guessing RETRACTION- e.g. cases (2 8 28) Closest known cases: (19) (YES) (CA_INF_DUCTAL) (33) (YES) (CA_INF_DUCTAL) (26) (YES) (CA_INF_DUCTAL) (28) (YES) (CAJNF_DUCTAL) (18) (YES) (CA) YES has been concluded or guessed for MALIGNANT? Speculating: DIAGNOSIS ... CA? CAJNF ..DUCTAL?

[Fertig, 1990]. An ordered list of these very-close points is returned as fetch's value.

generalize maps an .C to a r: it takes an ordered list of feature-tuples and "compresses" them into a single new feature-tuple. The weighter a r and the closer it is to the top of the list, the larger the contribution its attribute-value pairs make to the combined r returned by generalize. Suppose we query on the r (name apple), and suppose that M holds one hundred individual ap­ ples, half red and half yellow; a generalize operation over a list consisting of one hundred apples, half red and half yellow, yields a single r that might look like our second example above.

project maps a r to a r: given a feature-tuple it returns a new tuple constructed from a subset of the features in the original. While project is a purely syntactic opera­ tion, it is used by higher level operations (see the dis­ cussion of refocus below) to change contexts; the system focusses on those attributes and values that are deemed "interesting" 3 , temporarily ignoring other information on hand.

2.3 The basic cycle

Given this three-instruction virtual machine, how does the system operate? The basic cycle is two phase: (1) extend the current r; (2) choose a new current r, andre­ peat. Step one is implemented by an extend( r) function that is defined in terms of fetch and generalize. Step two is implemented by refocus which is defined in terms of all three.

To extend a r - to discover new implications given our database of cases and paradigms - we begin by ex­ ecuting the operation generalize(fetch(M, r)), where M is the database. If r, for example, describes a partic­ ular patient, fetch(M, r) will return a list of remem­ bered r's that are close to (similar to or reminiscent of) this particular patient; executing generalize over this list will produce an amalgam of all these remembered cases. Any highly-focussed and sufficiently-weighty values. can be classified as conclusions: if the memories exammed by generalize mainly have a value of "blonde" for at­ tribute "hair-color", say, the system will conclude that (hair-color blonde) is likely to characterize this case as well . It reports (hair-color blonde) to the user as a conclusion and augments the current r with this new attribute-value pair. The system attempts to conclude any value turned up by the fetch-generalize combination which hasn't yet been seen in the context of the cur­ rent query. · Values which contradict 4 are withdrawn; the user's input always takes precedence over system guesses. The extend operation is complete when all values that can be concluded have been and all contradictions re­ moved.

3 The system uses the evocativeness values calculated by fetch to determine which features are interesting.

· As expected, two distinct values of a boolean-typed at­ tribute always contradict. System-concluded values of other types of attributes contradict only if this information is spec­ ified in the attribute's distance metric. See [Fertig, 1990] for more details.

2.3.1 Simulated speculation

Refocus is then invoked over the extended r. Its role is to examine a r and refocus attention from this entire T to one (possibly small and conceivably unrepresentative) part of it. This element considered in isolation may serve as a seed for a new set of inferences. We call this process "simulated speculation." refocus may choose no, one or many data points; each chosen dat~ point becon:es the current r in turn. The more evocattve a data pomt with respect to the goal-the more sharply-defi.ned ~he cases nearby a r consisting only of that data pomt wtth respect to the goal attribute, in other words-the likelier target for refocus. The more sharply a data point stands out from the pack-by assumption it won't stand out clearly enough to qualify as a conclusion, but there are many intermediate shadings here-the likelier a refocus target .

Typically, the system will examine each o~ a small set of values associated with a particular attnbute whose value if known would focus the search space consid­ erabl~. The system performs the basic f etch-generalize cycle on each of these seed-tuples and is left with a set of regions in vector-space. One may be much closer to the original query than the others and may therefore be mergeable with it. The reader can. see the system'~ ?e­ havior during several refocus expenments by exammmg the transcript shown in figure 1. refocus first announces the attribute projected to, followed by any values ten­ tatively guessed as the result of the speculation experi­ ment. It then gives pointers to specific cases that both have this value and also resemble the rest of the user's input.

The system can operate in various modes; in ~he ~x­ ample given the basic cycle is repeated after c~nstdenng each attribute of the presented case. After allmput has been considered, the system will execute the basic cy:le one final time. It is then in a position to present a hst of the closest cases in the database given all the input and project to any undetermined goal attributes in one final attempt to determine values or at least narrow the space of possibilities.

Why should simulated speculation lead to more acc~­ rate performance? As a user enters a case the system ts automatically calculating a weight for individual features based on their evocativeness, or how closely they focus the search space with respect to the goal attribute .. In statistical terms we can think of the system as treatmg all features othe; than the goal as independent variables and the goal as the dependent variable. The system is automatically calculating a weight for each non-goal feature in isolation, in essence making the simplifying assumption that it is dealing with a simple bivariate dis­ tribution. Of course this isn't correct; in fact each case is better thought of as a many-internal multivar!able data point in which no feature can be labelled a przorz as. de­ pendent. And as in any multivariable case, correlatiOns between any two features may be artifacts that disap­ pear when seen in the context of addition~! variable~. The weighting of individual features accord.mg ~o a bt­ variate model is essentially a useful approx1mat10n but not guaranteed to be accurate. It will lead to inaccu-

~ate retrieval when the impact of one feature (variable) ~s enhanced or diminished considerably when it appears m the context of one or more others.

The heuristic approximation of feature salience by treating each feature as the independent variable in a bi­ variate model is a useful approximating device that fails to capture in its calculation important combinations of features. It is clear that we cannot calculate a salience score for each subset of all possible features. The cost is exponential and is clearly impractical for domains in which cases consist of more than a handful of features. However, we may be able to identify subsets of features that are important when considered together through the judicious use of simulated speculation.

For example, consider what happens when the system sets aside its standard processing and speculates on an undetermined goal feature . The system first collects all the values for that feature that appear among the cases currently judged to be close. Then a fetch is performed on each of these values and yields a profile (i.e. a gen­ eralized r) in which some (other) features are strongly associated with that value. Since now the mapping is one-to-many there is no danger of hidden interactions among the features masking or spuriously adding to the im~ortanc~ of any single feature, and those strongly as­ sociated w1th one goal value and not with others are good markers for the presence of that value. Those that appear in all or most of the retrieved profiles are bad or completely ineffective markers.

As outlined, simulated speculation can help the system adjust the feature salience measures crucial to effective retrieval of relevant cases. In so doing it improves ac­ curacy. Simulated speculation also improves efficiency, that is how quickly it converges on a list of relevant case~ and d~te~mines the values for all goal features (if possible). Similated speculation may narrow the search space directly by eliminating from further consideration at least temporarily, potential goal values that are incon~ sistent with the case as currently entered. The subsets of features which are discovered to be strongly associated with potential goal values provide an automatic standard by which to judge whether the current case is consistent with that goal value.

Finally, simulated speculation provides a road map for further processing. Among the features strongly associ­ ated with a goal may be some about which nothing has been entered. Directing its attention to these, and using the same refocus operation, the system may be able to determine the probable values for one or more of these n~n-goal features that are nevertheless highly correlated with the goal. In so doing it will have moved a significant step closer to pinpointing the goal. Even if unsuccess­ ful on its own, the system can ask the user if he knows the value for any of these correlated features and thus engage in a reasonable directed dialogue.

2.4 Higher-level operations

An ~nteresting and useful collection of higher-level op­ eratiOns can be based on these primitives. We have seen one, refocus, which is central to our attempt to simulate speculation. Others are discussed in [Fertig and Gelernter, 1989; Fertig, 1990]. The primitive oper­ ations have proven sufficient to allow the FGP machine to assemble intelligent sequences of database retrieval out of individual comparisons, performing if necessary a large number of individual analyses in an attempt to converge on a goal. The results discussed in the next section along with the example transcript illustrate the power of this structure-simple primitives, more compli­ cated strategies-in achieving a measure of qualitative and quantitative expertise.

3 Experiments

This section discusses experiments performed with the implemented (serial) version of the FGP syst~m .

The experiments were conducted on case databases in three domains: descriptions of mammograms collected at Yale-New Haven hospital, Fisher's Iris plant database [Fisher, 1936], and a collection of international folk dance descriptions. 5 These datasets are described below.

We wanted to validate the FGP system performance in three ways. First, we wanted to verify that the higher-level operations such as refocus worked as in­ tended. Recall that all FGP operations are built re­ cursively from the three primitive operations fetch, gen­ eralize, and project. The behavior of fetch depends not only on the syntactic structure of the inputs to the op­ eration but also on the domain information contained in the database. This semantic dependency makes testing any implementation of an FGP machine on synthetic data only partially effective. Real data from real do­ mains must be used to exercise the various component operations in the algebra.

We also wanted to quantify the performance of the fin­ ished system. Although we do not intend for FGP sys­ tems to be used solely or even primarily as stand alone diagnostic systems, accuracy in a diagnostic task is an easily understood metric and probably the most com­ monly used to compare the performance of automatic classifiers and expert systems to that of human experts. For this reason, we've chosen diagnostic accuracy as the primary quantitative measure to be used in the three domains.

Measures of qualitative behavior are our third and fi­ nal means of measuring the system's performance. As we've stressed, an FGP system is intended to be used as an interactive tool that can suggest plausible hypotheses and appropiate comments as information about a case is entered. This kind of behavior is hard to assess quan­ titatively. Nonetheless, we have made an attempt and have developed a metric to measure the system's rough qualitative behavior in the radiology domain.

3.1 Folk Dances

The first context in which discuss the FGP machine's accuracy is the one in which a reasonable size database and domain expert first presented themselves. Problem: Determine the nationality of a previously unseen folk ?a~ce given a list of other attributes (such as whether It IS done by couples or in fours, in a circle or a line, etc). The database has 643 cases spanning 46 different nationalities; the average number of features per case is 3.6.

5 We thank Jonathan Young for providing this database.

As reported in [Fertig and Gelernter, 1989], we pre­ sented 50 test cases for the FG P machine to classify. The domain expert, who happened to be the creator and maintainer of the database, answered correctly 53% of the time. The prototype determined the correct na­ tionality 57% of the time overall. Note that the classi­ fication task is not trivial given the number of possible classes and the sparseness of the training data. The per­ formance of both the domain expert and the program is quite good although under 60% correct in an absolute sense.

We applied the current version of the FGP machine, which incorporates a working implementation of the re­ focus operation, to the same database and task to deter­ mine if "simulated speculation" could improve accuracy. We found that it did: the FGP machine was able to de­ termine the correct nationality 65% of the time overall. The system was successful in 8 of 13 attempts to use re­ focus to determine the dance's nationality when it failed to draw a conclusion from the input directly. The FGP machine also used refocus to guess the values of other attributes much as seen in figure 1. These operations are harder to quantify, as many test cases are missing attributes. We were able to conclude, however, that the system guessed either a correct or consistent 6 value in 60% of these refocus experiments. The guess was clearly wrong 17% of the time.

3.2 Irises

Our second application is in the domain of plant iden­ tification. R.A. Fisher's data on three types of iris [Fisher, 1936] is often cited in the pattern recogni­ tion literature, and has become a de facto performance benchmark for new classification systems [Gates, 1972; Duda and Hart, 1973; Dasarathy, 1980]. Following the example of the previous studies, we randomly divided the Iris db into two partitions (of size 120 and 30), mak­ ing sure to include equal numbers from each class in both the training and test partitions.

Table 2 gives the basic result. The FGP machine cor­ rectly classifies 23 out of 30 of the test cases (76.6%), slightly improving on the performance of Dasarathy's Neighborhood Census Rule algorithm (Table 1), the best-performing of the nearest neighbor arproaches [Freeman, 1969; Gates, 1972; Dasarathy, 1980 .

Dasarathy allowed his system to choose a simple "don't know" option if none of the known categories was closer than some parameterized threshold. The FGP sys­ tem's ability to suggest multiple categories when unable to classify an item unambiguously is similar although often more informative. Suggesting a few possible cate­ gories is equivalent to ruling many categories out. This behavior is meant to capture an expert's ability to re­ serve judgement when faced with an unusual combination of facts, while still ordering past experiences in re­ lation to the new situation.

6 A value was judged consistent if it appeared in a majority of the cases in the database with the same nationality as the testcase.

3.3 Radiology

The current prototype has also been tested against a small database of patient records, descriptions of mam­ mograms. There were originally 88 records in the database; 20 cases were reserved for testing and 67 were used to seed the system, spanning 13 possible diagnoses (one of these 13 possibilities was the diagnosis normal, meaning no disease present). 7 The system was presented with the 20 test cases and asked to judge if a malignant lesion was indicated, and if so to determine a specific di­ agnosis. As discussed above, the system would present a short list (:::;4) of possible diagnoses if unable to decide on one with certainty.

The domain expert was the radiologist who had com­ piled the database. 8 Working from the descriptions of the mammograms alone, he accurately judged the ma­ lignancy of the testcases at the 68% level. The system performed slightly worse at 63%. However the system outperformed the domain expert in producing a differ­ ential diagnosis, with the right answer being stated out­ right or appearing in a short list of possibilities ( <= 3) 70% of the time to the clinician's 60% correct perfor­ mance.

3.3.1 Measuring qualitative performance

As we have discussed, we wanted the FGP system to exhibit qualitative expertise as well as quantitative ac­ curacy. We developed the refocus operation to model the human propensity to set aside §oat-directed think­ ing in the face of evocative events. We have labeled the FGP system's ability to behave similarly "simulated speculation." We discussed it in the context of both the folk dance experiment and figure 1. Still, we would like to quantify the system's qualitative performance, and in particular the usefulness of simulated speculation.

1 One record was thrown out because no diagnostic infor­ mation was included.

8 Dr. Paul Fisher of the Department of Diagnostic Radiol­ ogy, Yale University School of Medicine. Dr. Fisher's clinical specialty is mammography.

9 We present no evidence for this propensity as it is tauto­ logically beyond question: an event could not, by definition, be evocative if it did not cause the observer to stop and take notice.

We took two approaches: First, measure the absolute improvement in classification accuracy when simulated speculation is enabled. As reported, the FGP system's accuracy improved from 57 to 65% correct in the folk dance experiment, for a 14% gain. The system's per­ formance is identical with or without speculation when applied to the Iris test, a fact we expected given the extremely small number of features per case. Prelimi­ nary results indicate an 8% improvement in the radiology domain. 10 Note that the improvement in any domain is on precisely the most difficult cases. Refocus is only in­ voked when the direct evidence for choosing one value over another is underwhelming or nonexistent.

Second, we wanted to measure whether simulated speculation caused the system to make appropiate com­ ments "in about the right places and at the right times." To test this, we asked the domain expert to provide us with an audio tape of his analysis of five of the x-rays chosen at random. We presented the same five to the FG P machine and then placed the transcripts side-by­ side.

We then counted how often the FGP system and do­ main expert agreed that a particular feature indicated a malignant or benign condition in the patient . The sys­ tem agreed on 18 of the 24 times the expert chose to mention that a particular feature indicated malignancy or its opposite. The system made this type of comment at a total of 16 junctures where the expert said noth­ ing, but these comments were clearly inappropiate in 3 places only (in the opinion of the domain expert). While preliminary, we are encouraged by this concordance of opinion.

4 Related Work

The idea of retrieval based upon similarity is crucial to our system's ability to select a few relevant cases from a dense and extensive database, an idea exploited by re­ search in case-based reasoning, analogy and information retrieval. [Fertig, 1990] provides an extensive literature rev1ew.

5 Work in Progress

Although it is built to be reasonably efficient, the current FG P machine is inadequate to handle case databases of more than 1000 records assuming 10-20 features per case. The technique is intended specifically for use with large databases-the larger the better. Generating transcripts like the ones in the figures requires repeated computa­ tions against many or all elements in the database. Stan­ dard indexing strategies are useful to some extent, but in this problem (unlike the keyword-based text retrieval problem, for example), the database is likely to be fairly homogeneous, with most features present in most cases.

10 The numbers reported above for the radiology experi­ ment are with "speculation" enabled.

It's clear that if this program is to perform well, we must be able to execute operations involving large portions of large databases quickly. Parallel programming tech­ niques explored by members of the Linda group at Yale are a promising approach (e.g. [Carriero and Gelernter , 1988], and we are currently applying these techniques to a new implementation of the FGP machine.