Case-Based Reasoning. Research and Development

Translational bioinformatics is bioinformatics applied to human health. Although, up to now, its main focus has been to support molecular medicine research, translational bioinformatics has now the opportunity to design clinical decision support systems based on the combination of -omics data and internet-based knowledge resources. The paper describes the state-of-art of translational bioinformatics highlighting challenges and opportunities for decision support tools and case-based reasoning. It finally reports the design of a new system for supporting diagnosis in dilated cardiomyopathy. The system is able to combine text mining, literature search and case-based retrieval.

In this talk, we discuss and illustrate links existing between knowledge discovery in databases (KDD), knowledge representation and reasoning (KRR), and case-based reasoning (CBR). KDD techniques especially based on Formal Concept Analysis (FCA) are well formalized and allow the design of concept lattices from binary and complex data. These concept lattices provide a realistic basis for knowledge base organization and ontology engineering. More generally, they can be used for representing knowledge and reasoning in knowledge systems and CBR systems as well.

User-generated content is everywhere: photos, videos, news, blogs, art, music, and every other type of digital media on the Social Web. Games are no exception. From strategy games to immersive virtual worlds, game players are increasingly engaged in creating and sharing nearly all aspects of the gaming experience: maps, quests, artifacts, avatars, clothing, even games themselves. Yet, there is one aspect of computer games that is not created and shared by game players: the AI. Building sophisticated personalities, behaviors, and strategies requires expertise in both AI and programming, and remains outside the purview of the end user.

To understand why authoring Game AI is hard, we need to understand how it works. AI can take digital entertainment beyond scripted interactions into the arena of truly interactive systems that are responsive, adaptive, and intelligent. I will discuss examples of AI techniques for character-level AI (in embedded NPCs, for example) and game-level AI (in the drama manager, for example). These types of AI enhance the player experience in different ways. The techniques are complicated and are usually implemented by expert game designers.

I propose an alternative approach to designing Game AI: Real-Time CBR. This approach extends CBR to real-time systems that operate asynchronously during game play, planning, adapting, and learning in an online manner. Originally developed for robotic control, Real-Time CBR can be used for interactive games ranging from multiplayer strategy games to interactive believable avatars in virtual worlds.

As with any CBR technique, Real-Time CBR integrates problem solving with learning. This property can be used to address the authoring problem. I will show the first Web 2.0 application that allows average users to create AIs and challenge their friends to play them—without programming. I conclude with some thoughts about the role of CBR in AI-based Interactive Digital Entertainment.

The need for automated text evaluation is common to several AI disciplines. In this work, we explore the use of Machine Translation (MT) evaluation metrics for Textual Case Based Reasoning (TCBR). MT and TCBR typically propose textual solutions and both rely on human reference texts for evaluation purposes. Current TCBR evaluation metrics such as precision and recall employ a single human reference but these metrics are misleading when semantically similar texts are expressed with different sets of keywords. MT metrics overcome this challenge with the use of multiple human references. Here, we explore the use of multiple references as opposed to a single reference applied to incident reports from the medical domain. These references are created introspectively from the original dataset using the CBR similarity assumption. Results indicate that TCBR systems evaluated with these new metrics are closer to human judgements. The generated text in TCBR is typically similar in length to the reference since it is a revised form of an actual solution to a similar problem, unlike MT where generated texts can sometimes be significantly shorter. We therefore discovered that some parameters in the MT evaluation measures are not useful for TCBR due to the intrinsic difference in the text generation process.

Interpreting time series of measurements and exploring a repository of cases with time series data looking for similarities, are non-trivial, but very important tasks.

Classical methodological solutions proposed to deal with (some of) these goals, typically based on mathematical techniques, are characterized by strong limitations, such as unclear or incorrect retrieval results and reduced interactivity and flexibility.

In this paper, we describe a novel case base exploration and retrieval architecture, which supports time series summarization and interpretation by means of Temporal Abstractions, and in which multi-level abstraction mechanisms and proper indexing techniques are provided, in order to grant

expressiveness

in issuing queries, as well as

efficiency

and

flexibility

in answering queries themselves.

Relying on a set of concrete examples, taken from the haemodialysis domain, we illustrate the system facilities, and we demonstrate the advantages of relying on this methodology, with respect to more classical mathematical ones.

This paper presents an algorithm of adaptation for a case-based reasoning system with cases and domain knowledge represented in the expressive description logic

$\mathcal{ALC}$

. The principle is to first pretend that the source case to be adapted solves the current target case. This may raise some contradictions with the specification of the target case and with the domain knowledge. The adaptation consists then in repairing these contradictions. This adaptation algorithm is based on an extension of the classical tableau method used for deductive inference in

$\mathcal{ALC}$

.

The concept of diversity was successfully introduced for recommender-systems. By displaying results that are not only similar to a target problem but also diverse among themselves, recommender systems have been shown to provide more effective guidance to the user. We believe that similar benefits can be obtained in case-based planning, provided that diversity-enhancement techniques can be adapted appropriately. Our claim is that diversity is truly useful when it refers not only to the initial and goal states of a plan, but also to the sequence of actions the plan consists of. To formalize this characteristic and support our claim, we define the metric of “plan diversity” and put it to test using plans for a real-time strategy game, a domain chosen for the simplicity and clarity of its tasks and the quantifiable results it generates.

In this paper we present an approach for reducing the memory footprint requirement of temporal difference methods in which the set of states is finite. We use case-based generalization to group the states visited during the reinforcement learning process. We follow a lazy learning approach; cases are grouped in the order in which they are visited. Any new state visited is assigned to an existing entry in the Q-table provided that a similar state has been visited before. Otherwise a new entry is added to the Q-table. We performed experiments on a turn-based game where actions have non-deterministic effects and might have long term repercussions on the outcome of the game. The main conclusion from our experiments is that by using case-based generalization, the size of the Q-table can be substantially reduced while maintaining the quality of the RL estimates.

This paper addresses the issue of adapting cases represented by plain text with the help of formal concept analysis and natural language processing technologies. The actual cases represent recipes in which we classify ingredients according to culinary techniques applied to them. The complex nature of linguistic anaphoras in recipe texts make usual text mining techniques inefficient so a stronger approach, using syntactic and dynamic semantic analysis to build a formal representation of a recipe, had to be used. This representation is useful for various applications but, in this paper, we show how one can extract ingredient–action relations from it in order to use formal concept analysis and select an appropriate replacement sequence of culinary actions to use in adapting the recipe text.

Increasingly, in our everyday lives, we rely on our ability to access and understand complex information. Just as the search engine played a key role in helping people access relevant information, there is evidence that the next generation of information tools will provide users with a greater ability to analyse and make sense of large amounts of raw data. Visualization technologies are set to play an important role in this regard. However, the current generation of visualization tools are simply too complex for the typical user. In this paper we describe a novel application of case-based reasoning techniques to help users visualize complex datasets. We exploit an online visualization service, ManyEyes, and explore how case-based representation of datasets including simple features such as size and content types can produce recommendations to assist novice users in the selection of appropriate visualization types.

In this paper we study the topic of CBR systems learning from observations in which those observations can be represented as stochastic policies. We describe a general framework which encompasses three steps: (1) it observes agents performing actions, elicits stochastic policies representing the agents’ strategies and retains these policies as cases. (2) The agent analyzes the environment and retrieves a suitable stochastic policy. (3) The agent then executes the retrieved stochastic policy, which results in the agent mimicking the previously observed agent. We implement our framework in a system called JuKeCB that observes and mimics players playing games. We present the results of three sets of experiments designed to evaluate our framework. The first experiment demonstrates that JuKeCB performs well when trained against a variety of fixed strategy opponents. The second experiment demonstrates that JuKeCB can also, after training, win against an opponent with a dynamic strategy. The final experiment demonstrates that JuKeCB can win against "new" opponents (i.e. opponents against which JuKeCB is untrained).

The utility problem occurs when the performance of learning systems degrade instead of improve when additional knowledge is added. In lazy learners this degradation is seen as the increasing time it takes to search through this additional knowledge, which for a sufficiently large case base will eventually outweigh any gains from having added the knowledge. The two primary approaches to handling the utility problem are through efficient indexing and by reducing the number of cases during case base maintenance. We show that for many types of practical case based reasoning systems, the encountered case base sizes do not cause retrieval efficiency to degrade to the extent that it becomes a problem. We also show how complicated case base maintenance solutions intended to address the utility problem can actually decrease the combined system efficiency.

The task of building labelled case bases can be approached using active learning (AL), a process which facilitates the labelling of large collections of examples with minimal manual labelling effort. The main challenge in designing AL systems is the development of a selection strategy to choose the most informative examples to manually label. Typical selection strategies use exploitation techniques which attempt to refine uncertain areas of the decision space based on the output of a classifier. Other approaches tend to balance exploitation with exploration, selecting examples from dense and interesting regions of the domain space. In this paper we present a simple but effective exploration-only selection strategy for AL in the textual domain. Our approach is inherently case-based, using only nearest-neighbour-based density and diversity measures. We show how its performance is comparable to the more computationally expensive exploitation-based approaches and that it offers the opportunity to be classifier independent.

The performance of a Textual Case-Based Reasoning system is critically dependent on its underlying model of text similarity, which in turn is dependent on similarity between terms and phrases in the domain. In the absence of human intervention, term similarities are often modelled using co-occurrence statistics, which are fragile unless the corpus is truly representative of the domain. We present the case for introspective revision in TCBR, whereby the system incrementally revises its term similarity knowledge by exploiting conflicts of its representation against an alternate source of knowledge such as category knowledge in classification tasks, or linguistic and background knowledge. The advantage of such revision is that it requires no human intervention. Our experiments on classification knowledge show that revision can lead to substantial gains in classification accuracy, with results competitive to best-in-line text classifiers. We have also presented experimental results over synthetic data to suggest that the idea can be extended to improve case-base alignment in TCBR domains with textual problem and solution descriptions.

Acquiring adaptation knowledge for case-based reasoning systems is a challenging problem. Such knowledge is typically elicited from domain experts or extracted from the case-base itself. However, the ability to acquire expert knowledge is limited by expert availability or cost, and the ability to acquire knowledge from the case base is limited by the the set of cases already encountered. The WebAdapt system [20] applies an alternative approach to acquiring case knowledge, using a knowledge planning process to mine it as needed from Web sources. This paper presents two extensions to WebAdapt’s approach, aimed at increasing the method’s generality and ease of application to new domains. The first extension applies introspective reasoning to guide recovery from adaptation failures. The second extension applies reinforcement learning to the problem of selecting knowledge sources to mine, in order to manage the exploration/exploitation tradeoff for system knowledge. The benefits and generality of these extensions are assessed in evaluations applying them in three highly different domains, with encouraging results.

In real world applications, interested concepts are more likely to change rather than remain stable, which is known as

concept drift

. This situation causes problems on predictions for many learning algorithms including case-base reasoning (CBR). When learning under concept drift, a critical issue is to identify and determine “when” and “how” the concept changes. In this paper, we developed a

competence-based empirical distance

between case chunks and then proposed a change detection method based on it. As a main contribution of our work, the change detection method provides an approach to measure the distribution change of cases of an infinite domain through finite samples and requires no prior knowledge about the case distribution, which makes it more practical in real world applications. Also, different from many other change detection methods, we not only detect the change of concepts but also quantify and describe this change.

In CBR the design and selection of similarity measures is paramount. Selection can benefit from the use of exploratory visualisation-based techniques in parallel with techniques such as cross-validation accuracy comparison. In this paper we present the Case Base Topology Viewer (CBTV) which allows the application of different similarity measures to a case base to be visualised so that system designers can explore the case base and the associated decision boundary space. We show, using a range of datasets and similarity measure types, how the idiosyncrasies of particular similarity measures can be illustrated and compared in CBTV allowing CBR system designers to make more informed choices.

The vast majority of research on AI planning has focused on automated plan recognition, in which a planning agent is provided with a set of inputs that include an initial goal (or set of goals). In this context, the goal is presumed to be static; it never changes, and the agent is not provided with the ability to reason about whether it should change this goal. For some tasks in complex environments, this constraint is problematic; the agent will not be able to respond to opportunities or plan execution failures that would benefit from focusing on a different goal.

Goal driven autonomy

(GDA) is a reasoning framework that was recently introduced to address this limitation; GDA systems perform anytime reasoning about what goal(s) should be satisfied [4]. Although promising, there are natural roles that case-based reasoning (CBR) can serve in this framework, but no such demonstration exists. In this paper, we describe the GDA framework and describe an algorithm that uses CBR to support it. We also describe an empirical study with a multiagent gaming environment in which this CBR algorithm outperformed a rule-based variant of GDA as well as a non-GDA agent that is limited to dynamic replanning.

In Case Based Reasoning (CBR), case retrieval is generally guided by similarity. However, the most similar case may not be the easiest one to adapt, and it may be helpful to also use an adaptability criterion to guide the retrieval process. The goal of this paper is twofold: First, it proposes a method of case retrieval that relies simultaneously on similarity and adaptation costs. Then, it illustrates its use by integrating adaptation cost into the Case Retrieval Net (CRN) memory model, a similarity-based case retrieval system. The described retrieval framework optimizes case reuse early in the inference cycle, without incurring the full cost of an adaptation step. Our results on a case study reveal that the proposed approach yields better recall accuracy than CRN’s similarity only-based retrieval while having similar computational complexity.

How to reuse or adapt past solutions to new problems is one of the least understood problems in case-based reasoning. In this paper we will focus on the problem of how to combine solutions coming from multiple cases in search-based approaches to reuse. For that purpose, we introduce the notion of

amalgam

. Assuming the solution space can be characterized as a generalization space, an amalgam of two solutions is a third solution which combines as much as possible from the original two solutions. In the paper we define amalgam as a formal operation over terms in a generalization space, and we discuss how amalgams may be applied in search-based reuse techniques to combine case solutions.

We envisage retrieval in textual case-based reasoning (TCBR) as an instance of abductive reasoning. The two main subtasks underlying abductive reasoning are ‘hypotheses generation’ where plausible case hypotheses are generated, and ‘hypothesis testing’ where the best hypothesis is selected among these in sequel. The central idea behind the presented two-stage retrieval model for TCBR is that recall relies on lexical equality of features in the cases while recognition requires mining higher order semantic relations among features. The proposed account of recognition relies on a special representation called

random indexing

, and applies a method that simultaneously performs an

implicit dimension reduction

and discovers

higher order relations

among features based on their meanings that can be learned

incrementally

. Hence, similarity assessment in recall is computationally less expensive and is applied on the whole case base while in recognition a computationally more expensive method is employed but only on the case hypotheses pool generated by recall. It is shown that the two-stage model gives promising results.

There has been a recent interest in the Web as a very promising source of cases for CBR applications. This paper describes some alternatives that could be exploited to include these sources of cases in real CBR systems. A theoretical framework is presented that categorizes different approaches to exploit Web sources for populating the case base or obtaining the background knowledge required to perform the retrieval and adaptation stages. Finally, we introduce a real CBR system that uses Web knowledge to improve the reasoning cycle.

Case-Based Reasoning (CBR) solves problems by reusing past problem-solving experiences maintained in a casebase. The key CBR knowledge container therefore is its casebase. However there are further containers such as similarity, reuse and revision knowledge that are also crucial. Automated acquisition approaches are particularly attractive to discover knowledge for such containers. Majority of research in this area is focused on introspective algorithms to extract knowledge from within the casebase. However the rapid increase in Web applications has resulted in large volumes of user generated experiential content. This forms a valuable source of background knowledge for CBR system development. In this paper we present a novel approach to acquiring knowledge from Web pages. The primary knowledge structure is a dynamically generated taxonomy which once created can be used during the retrieve and reuse stages of the CBR cycle. Importantly this taxonomy is pruned according to a clustering-based sense disambiguation heuristic that uses similarity over the solution vocabulary of cases. Algorithms presented in the paper are applied to several online FAQ systems consisting of textual problem-solving cases. The goodness of generated taxonomies is evidenced by improved semantic comparison of text due to successful sense disambiguation resulting in higher retrieval accuracy. Our results show significant improvements over standard text comparison alternatives.

An approach to enhancement of case-based reasoning in situations where substantial amounts of the knowledge are expressed as informal or “folk” arguments is applied to the authentication (dating) of paintings. It emphasizes knowledge acquisition templates, indexing through numerical taxonomy and close attention to typing of the arguments. This work has shown that even simple types can be regarded as attributes of the arguments, hence attributes of their cases. The cases are then organized and retrieved through structuring of the case bases by methods of numerical taxonomy. Expertise expressed as texts of detailed reports on dating of paintings from historical and chemical knowledge is the source material from which the cases are constructed. Case bases with and without folk-argument knowledge, for the same paintings, are compared for their ability to assign correct date ranges. In this test, the performance of the case base containing argument knowledge is consistently superior.

Most of the recent literature on complexity measures in textual case-based reasoning examined alignment between problem space and solution space, which used to be an issue of formulating CBR hypothesis. However, none of existing complexity measures could dispel the specter of predefined class label that does not appear in public textual datasets available, or clarify the correctness of the proposed solutions in the retrieved cases most similar to a target problem. This paper presented a novel alignment measure to circumvent these difficulties by calculating rank correlation between most similar case rankings in problem space and most similar case rankings in solution space. We also examined how to utilize existing alignment measures for textual case retrieval and textual case base maintenance. Empirical evaluation on Aviation Investigation Reports from Transportation Safety Board of Canada showed that rank correlation alignment measure might become a promising method for case-based non-classification systems.

Microarray technology enables the simultaneous measurement of thousands of gene expressions, while often providing a limited set of samples. These datasets require data mining methods for classification, prediction, and clustering to be tailored to the peculiarity of this domain, marked by the so called ‘curse of dimensionality’. One main characteristic of these specialized algorithms is their intensive use of feature selection for improving their performance. One promising method for feature selection is Bayesian Model Averaging (BMA) to find an optimal subset of genes. This article presents BMA applied to gene selection for classification on two cancer gene expression datasets and for survival analysis on two cancer gene expression datasets, and explains how case based reasoning (CBR) can benefit from this model to provide, in a hybrid BMA-CBR classification or survival prediction method, an improved performance and more expansible model.

Precious collections of cultural heritage documents are available for study on the internet via web archives. The automatically added metadata on these scanned documents, are not sufficient to make a specific search. User effort is needed to add manual annotations in order to enhance document content accessibility and exploitability. Annotators have different experiences in dissimilar manuscript domains. Hence the reuse of users’ experiences is constructive to accelerate the annotation process and to correct user mistakes. In this article we present our digital archive model and a prototype to collaboratively annotate online ancient manuscripts. Our system tracks important user actions, and saves them as traces composed of hierarchical episodes. These episodes are considered as cases to be reused by a recommender system.

In this paper, we present a model for competency development using serious games, which is underpinned by a hierarchical case-based planning strategy. In our model, a learner’s objectives are addressed by retrieving a suitable learning plan in a two-stage retrieval process. First of all, a suitable abstract plan is retrieved and personalised to the learner’s specific requirements. In the second stage, the plan is incrementally instantiated as the learner engages with the learning material. Each instantiated plan is composed of a series of stories - interactive narratives designed to improve the learner’s competence within a particular learning domain. The sequence of stories in an instantiated plan is guided by the planner, which monitors the learner performance and suggests the next learning step. To create each story, the learner’s competency proficiency and performance assessment history are considered. A new story is created to further progress the plan instantiation. The plan succeeds when the user consistently reaches a required level of proficiency. The successful instantiated plan trace is stored in an experience repository and forms a knowledge base on which introspective learning techniques are applied to justify and/or refine abstract plan composition.

This paper presents an approach for the intelligent diagnosis and monitoring of business workflows based on operation data in the form of temporal log data. The representation of workflow related case knowledge in this research using graphs is explained. The workflow process is orchestrated by a software system using BPEL technologies within a service-oriented architecture. Workflow cases are represented in terms of events and their corresponding temporal relationships. The matching and CBR retrieval mechanisms used in this research are explained and the architecture of an integrated intelligent monitoring system is shown. The paper contains an evaluation of the approach based on experiments on real data from a university quality assurance exam moderation system. The experiments and the evaluation of the approach is presented and is shown that a graph matching based similarity measure is capable to diagnose problems within business workflows. Finally, further work on the system and the extension to a full intelligent monitoring and process optimisation system is presented.

Automating the construction of multiple-choice questions (MCQs) is a challenge that has attracted the interest of artificial intelligence researchers for many years. We present a case-based reasoning (CBR) approach to this problem in which MCQs are automatically generated from cases describing events or experiences of interest (e.g., historical events, movie releases, sports events) in a given domain. Measures of interestingness and similarity are used in our approach to guide the retrieval of cases and case features from which questions, distractors, and hints for the user are generated in natural language. We also highlight a potential problem that may occur when similarity is used to select distractors for the correct answer in certain types of MCQ. Finally, we demonstrate and evaluate our approach in an intelligent system for automating the design of MCQ quizzes called AutoMCQ.

Creation and adaptation of workflows is a difficult and costly task that is currently performed by human workflow modeling experts. Our paper describes a new approach for the automatic adaptation of workflows, which makes use of a case base of former workflow adaptations. We propose a general framework for case-based adaptation of workflows and then focus on novel methods to represent and reuse previous adaptation episodes for workflows. An empirical evaluation demonstrates the feasibility of the approach and provides valuable insights for future research.

This paper proposes an approach aimed at obviating empty answers for a family of conjunctive queries involving value constraints. Contrary to the approaches based on a relaxation of the predicates involved in the query, the principle suggested here consists in replacing the query by a similar one which has been processed previously and whose answer is known to be non-empty. This technique thus avoids the combinatory explosion induced by classical relaxation-based approaches.

myCBR

is a freely available tool for rapid prototyping of similarity-based retrieval applications such as case-based product recommender systems. It provides easy-to-use model generation, data import, similarity modelling, explanation, and testing functionality together with comfortable graphical user interfaces. SCOOBIE is an ontology-based information extraction system, which uses symbolic background knowledge for extracting information from text. Extraction results depend on existing knowledge fragments. In this paper we show how to use SCOOBIE for generating cases from texts. More concrete we use ontologies of the Web of Data, published as so called Linked Data interlinked with

myCBR

’s case model. We present a way of formalising a case model as Linked Data ready ontology and connect it with other ontologies of the Web of Data in order to get richer cases.

In previous papers we have presented our autonomous poker playing agent (

SARTRE

) that uses a

memory-based

approach to create a betting strategy for two-player, limit Texas Hold’em.

SARTRE

participated in the 2009 IJCAI Computer Poker Competition where the system was thoroughly evaluated by challenging a range of other computerised opponents. Since the competition

SARTRE

has undergone case-based maintenance. In this paper we present results from the 2009 Computer Poker Competition and describe the latest modifications and improvements to the system. Specifically, we investigate two claims: the first that

modifying the solution representation results in changes to the problem coverage

and the second that

different policies for re-using solutions leads to changes in performance

. Three separate

solution re-use policies

for making betting decisions are introduced and evaluated. We conclude by presenting results of self-play experiments between the

pre

and

post

maintenance systems.

Product recommendation systems are now a key part of many e-commerce services and have proven to be a successful way to help users navigate complex product spaces. In this paper, we focus on critiquing-based recommenders, which permit users to

tweak

the features of recommended products in order to refine their needs and preferences. In this paper, we describe a novel approach to reusing past critiquing histories in order to improve overall recommendation efficiency.

The behavior of a pervasive application is much improved with access to accurate, relevant information. While other users’ devices are a promising source of current information for pervasive applications, the relevance of information describing other users is not always apparent. To date, CBR has been successfully used to select information of relevance from the previous experience of the application’s user. This paper describes how CBR techniques can be used to select accurate, relevant information from other users as well. We address the challenges that arise due to the set of other users from which information is available being dynamic and potentially sparse, the potential pitfalls of completely ignoring the previous experience of the application’s user while using context from other users, and the elicitation of essential feedback distracting the potentially mobile user. This paper presents an examination of the use of information from other users through simulations run on three existing pervasive datasets.

Architects’ daily routine involves working with drawings. They use either a pen or a computer to sketch out their ideas or to do a drawing to scale. We therefore propose the use of a sketch-based approach when using the floor plan repository for queries. This enables the user of the system to sketch a schematic abstraction of a floor plan and search for floor plans that are structurally similar. We also propose the use of a visual query language, and a semantic structure as put forward by Langenhan. An algorithm extracts the semantic structure sketched by the architect on DFKI’s Touch& Write table and compares the structure of the sketch with that of those from the floor plan repository. The a.SCatch system enables the user to access knowledge from past projects easily. Based on CBR strategies and shape detection technologies, a sketch-based retrieval gives access to a semantic floor plan repository. Furthermore, details of a prototypical application which allows semantic structure to be extracted from image data and put into the repository semi-automatically are provided.

Grid scheduling performance is significantly affected by the accuracy of job runtime estimation. Since past performance is a good indicator of future trends, we use a case-based reasoning approach to predict the execution time, or run time, based on past experience. We first define the similarity of jobs and similarity of machines, and then determine which job and machine characteristics affect the run time the most by analyzing information from previous runs. We then create a case base to store historical data, and use the

TA3

case-based reasoning system to fetch all relevant cases from the case base. We apply this approach to schedule Functional Regression Tests for IBM

®

DB2

®

Universal Database

TM

(DB2 UDB) products. The results show that our approach achieves low runtime estimation errors and substantially improves grid scheduling performance.