US5717835A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Simple approach to case-based reasoning for data navigation tasks
Assignee: International Business Machines Corp
•
Filing: 1995-01-11
•
Granted: 1998-02-10
•
Expires: 2015-01-11
Abstract
Abstract An architecture and key algorithms are presented that simplify the implementation and improve the functionality of knowledge-based systems that employ case-based reasoning for data navigation tasks (e.g., solving help desk problems using a database of past problem instances). The various embodiments of the invention improve on the state-of-the-art in several respects: (a) provides greatly increased flexibility in choosing attributes relevant to a case in that choices are made dynamically at case acquisition instead of statically when the knowledge-based system is designed; (b) increased system flexibility and decreased system complexity by not requiring designers to specify the manner in which attribute values are compared; (c) simplified system design by avoiding the use of similarity metrics; (d) allows for the incremental acquisition of data in problem instances, instead of requiring that all potentially relevant data be collected; and (e) provides a way to explain why a problem solution was chosen. Case acquisition is accomplished by having end-users replay the steps taken to solve a problem instance. Each such step constitutes a navigation element that consists of: (i) a test expressing the conditions under which the navigation is done; (ii) a text description explaining the step; and (iii) a database query expressing the next navigation. Algorithms are presented for case acquisition, case retrieval, and case removal. The case repository is structured as a graph of navigation elements that, under appropriate circumstances, combines into a single node those navigation elements common to multiple cases.
Inventors
- 👤 Joseph Hellerstein
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 08:47
CPC Classifications
G; G06; G06N; G06N5/00; G06N5/02
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
108 words
A method of data navigation employing a knowledge system that uses case-based reasoning to compare a new problem instance with a case repository of past problem instances structured as an ordered set of navigation elements, said method comprising: communicating problem data for the new problem instance into the knowledge system; retrieving from the case repository a past problem instance relevant to the problem data; wherein a navigation element associated with the past problem instance comprises an ordered triple including: a test expressing data navigation conditions; a text description explaining the navigation element; and a query; and generating information about the new problem instance based on the navigation element.
Claim 2
Independent Claim
108 words
A method of data navigation employing a knowledge system that uses case-based reasoning to compare a new problem instance with a case repository of past problem instances structured as an ordered set of navigation elements, said method comprising: communicating problem data for the new problem instance into the knowledge system; retrieving from the case repository a past problem instance relevant to the problem data; wherein a navigation element associated with the past problem instance comprises an ordered triple including: a test expressing data navigation conditions; a text description explaining the navigation element; and a query; and generating information about the new problem instance based on the navigation element.
Claim 3
Dependent Claim
24 words
The method of claim 1 wherein the case repository comprises a directed graph structure wherein navigation elements common to past problem instances are combined.
Claim 4
Dependent Claim
38 words
The method of claim 1, wherein the query represents a database query indexing a next member in the ordered set of navigation elements, said method further comprising: retrieving the next member in the ordered set of navigation elements.
Claim 5
Dependent Claim
55 words
The method of claim 1, further comprising: collecting additional problem data which would make an additional past problem instance relevant to the new problem instance; and iterating said retrieving step and said collecting step until the new problem instance is resolved or all past problem instances relevant to the new problem instance have been retrieved.
Claim 6
Dependent Claim
24 words
The method of claim 4, further comprising: identifying an invalid past problem instance; and removing from the case repository the invalid past problem instance.
Claim 7
Dependent Claim
100 words
The method of claim 4 wherein said all past problem instances relevant to the new problem instance have been retrieved and none contain the solution to the new problem instance, further comprising: specifying a navigation element for input to the knowledge system; appending, responsive to said specifying step, the navigation element to an ordered set of navigation elements for the new problem instance; repeating said specifying step and said appending step until the new problem instance is resolved; and updating, responsive to said repeating step, the case repository with the ordered set of navigation elements for the new problem instance.
Claim 8
Dependent Claim
104 words
The method of claim 6 wherein the case repository is a data structure having a plurality of nodes referencing navigation elements and wherein said updating step further comprises: searching the case repository for a sequence of nodes referencing navigation elements which correspond to a sequence of the ordered set of navigation elements; revising, responsive to said searching step, the case repository to incorporate the new problem instance; incorporating a new node referencing navigation elements for an ordered navigation element not found in said searching step; and repeating said searching, revising, and incorporating steps until the new problem instance is added to the case repository.
Claim 9
Independent Claim
125 words
A method of generating a case repository of problem instances for use in a knowledge system for data navigation wherein said problem instances are structured as an ordered set of navigation elements stored in the case repository, comprising: specifying a navigation element corresponding to a new problem instance for input to the knowledge system, wherein the navigation element comprises an ordered triple including: a test expressing data navigation conditions: a text description explaining the navigation element; and a query; appending, responsive to said specifying step, the navigation element to the set of ordered navigation elements; repeating said specifying and appending steps until the problem instance is resolved; and updating the case repository with the ordered set of navigation elements corresponding to the new problem instance.
Claim 10
Independent Claim
125 words
A method of generating a case repository of problem instances for use in a knowledge system for data navigation wherein said problem instances are structured as an ordered set of navigation elements stored in the case repository, comprising: specifying a navigation element corresponding to a new problem instance for input to the knowledge system, wherein the navigation element comprises an ordered triple including: a test expressing data navigation conditions: a text description explaining the navigation element; and a query; appending, responsive to said specifying step, the navigation element to the set of ordered navigation elements; repeating said specifying and appending steps until the problem instance is resolved; and updating the case repository with the ordered set of navigation elements corresponding to the new problem instance.
Claim 11
Dependent Claim
106 words
The method of claim 8 wherein the case repository is a data structure having a plurality of nodes referencing navigation elements and wherein said updating step further comprises: searching the case repository for a sequence of nodes referencing navigation elements which correspond to a sequence of navigation elements for the new problem instance; revising a sequence of nodes found in said searching step to incorporate the new problem instance; incorporating a new node referencing navigation elements for an ordered navigation element not found in said searching step; and repeating said searching, updating, and incorporating steps until the new problem instance is added to the case repository.
Claim 12
Dependent Claim
120 words
A case-based knowledge system for data navigation having a processor adapted to compare a new problem instance with past problem instances, said system comprising: a case repository for storing the past problem instances wherein the past problem instances are structured as an ordered set of navigation elements; a case retrieval function for retrieving from the case repository, a past problem instance relevant to the new problem instance wherein a navigation element associated with the past problem instance is an ordered triple including: a test expressing data navigation conditions; a text description explaining the navigation element; and a query; and a user interface for routing the new problem instance to, and a retrieved past problem instance from, the case retrieval function.
Claim 13
Dependent Claim
120 words
A case-based knowledge system for data navigation having a processor adapted to compare a new problem instance with past problem instances, said system comprising: a case repository for storing the past problem instances wherein the past problem instances are structured as an ordered set of navigation elements; a case retrieval function for retrieving from the case repository, a past problem instance relevant to the new problem instance wherein a navigation element associated with the past problem instance is an ordered triple including: a test expressing data navigation conditions; a text description explaining the navigation element; and a query; and a user interface for routing the new problem instance to, and a retrieved past problem instance from, the case retrieval function.
Claim 14
Dependent Claim
19 words
The system of claim 10 wherein the user interface routes the new problem instance to and from related applications.
Claim 15
Dependent Claim
46 words
The system of claim 10 wherein the the query represents a database query for retrieving a next member in the ordered set of navigation elements, said system further comprising: means for generating a database query indexing a next member in the ordered set of navigation elements.
Claim 16
Dependent Claim
68 words
The system of claim 10, further comprising: said case retrieval function including logic for iteratively retrieving from the case repository, all past problem instances relevant to the new problem instance and all past problem instances whose relevance is dependent upon receiving additional new problem instance data, until the new problem instance is resolved or said all past problem instances relevant to the new problem instance have been retrieved.
Claim 17
Dependent Claim
30 words
The system of claim 13, further comprising: means for identifying an invalid past problem instance, a case removal function for removing the invalid past problem instance from the case repository.
Claim 18
Dependent Claim
24 words
The system of claim 10 wherein the case repository comprises a directed graph structure wherein navigation elements common to past problem instances are combined.
Claim 19
Dependent Claim
83 words
The system of claim 15 wherein said all past problem instances relevant to the new problem instance have been retrieved and none contain the solution to the new problem instance, further comprising: a case acquisition function for creating an ordered set of navigation elements for the new problem instance and updating the case repository with the ordered set of navigation elements created; wherein the user interface is adapted to route the navigation elements for the new problem instance to the case acquisition function.
Claim 20
Dependent Claim
74 words
The system of claim 16 wherein the case repository is a data structure having a plurality of nodes referencing navigation elements and wherein said case acquisition function further comprises: means for iteratively searching and revising the case repository to incorporate a sequence of the navigation elements for the new problem instance common to past problem instances; wherein the ordered set of navigation elements for the new problem instance are added to the case repository.
Claim 21
Dependent Claim
123 words
A case-based knowledge system for data navigation having a processor adapted to compare a new problem instance with past problem instances, said system comprising: a case repository for storing the past problem instances as an ordered set of navigation elements; a case acquisition function for iteratively creating the ordered set of navigation elements corresponding to the new problem instance and updating the case repository with the ordered set of navigation elements created; wherein a navigation element associated with the new problem instance is an ordered triple including: a test expressing data navigation conditions; a text description explaining the navigation element; and a query, and a user interface adapted to route the navigation elements for the new problem instance to the case acquisition function.
Claim 22
Dependent Claim
123 words
A case-based knowledge system for data navigation having a processor adapted to compare a new problem instance with past problem instances, said system comprising: a case repository for storing the past problem instances as an ordered set of navigation elements; a case acquisition function for iteratively creating the ordered set of navigation elements corresponding to the new problem instance and updating the case repository with the ordered set of navigation elements created; wherein a navigation element associated with the new problem instance is an ordered triple including: a test expressing data navigation conditions; a text description explaining the navigation element; and a query, and a user interface adapted to route the navigation elements for the new problem instance to the case acquisition function.
Claim 23
Dependent Claim
24 words
The system of claim 18 wherein the case repository comprises a directed graph structure wherein navigation elements common to past problem instances are combined.
Claim 24
Dependent Claim
31 words
The system of claim 13 wherein the next member is a last navigation element which includes: a text description having a solution for the new problem instance; and a null query.
Claim 25
Dependent Claim
32 words
The system of claim 10, further comprising: means for invoking a program, coupled to the case retrieval function, to take an action based on the query to solve the new problem instance.
Claim 26
Dependent Claim
47 words
The system of claim 10, wherein the case repository of past problem instances is a database of information and the problem data includes an ad hoc database query; and said case retrieval function includes logic for querying the database and retrieving information relevant to the database query.
Claim 27
Dependent Claim
31 words
The method of claim 3, wherein the next member is a last navigation element which includes: a text description having a solution for the new problem instance; and a null query.
Claim 28
Dependent Claim
24 words
The method of claim 1, further comprising: invoking a program to take an action based on the query to solve the new problem instance.
Claim 29
Dependent Claim
49 words
The method of claim 1, wherein the case repository of past problem instances is a database of information, said method further comprising: said communicating problem data includes communicating an ad hoc database query; and said retrieving step includes querying the database and retrieving information relevant to the database query.
Claim 30
Dependent Claim
124 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for data navigation wherein a knowledge system uses case-based reasoning to compare a new instance with a case repository of past instances, said method steps comprising: communicating data for the new instance into the knowledge system; retrieving from the case repository a past instance relevant to the data; wherein the past instance is an ordered set of navigation elements and wherein a navigation element associated with the past instance comprises an ordered triple including: a test expressing data navigation conditions; a text description explaining the navigation element; and a query; and generating information about the new instance based on the navigation element.
Claim 31
Dependent Claim
124 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for data navigation wherein a knowledge system uses case-based reasoning to compare a new instance with a case repository of past instances, said method steps comprising: communicating data for the new instance into the knowledge system; retrieving from the case repository a past instance relevant to the data; wherein the past instance is an ordered set of navigation elements and wherein a navigation element associated with the past instance comprises an ordered triple including: a test expressing data navigation conditions; a text description explaining the navigation element; and a query; and generating information about the new instance based on the navigation element.
Claim 32
Dependent Claim
42 words
The program storage device of claim 26, wherein the query represents a database query indexing a next member in the ordered set of navigation elements, said method comprising the step of: retrieving the next member in the ordered set of navigation elements.
Claim 33
Dependent Claim
56 words
The program storage device of claim 26, said method further comprising the steps of: collecting additional data which would make an additional past instance relevant to the new instance; and iterating said retrieving step and said collecting step until the new instance is resolved or all past instances relevant to the new instance have been retrieved.
Claim 34
Dependent Claim
21 words
The program storage device of claim 27 wherein the next member is a last navigation element which includes a null query.
Claim 35
Dependent Claim
28 words
The program storage device of claim 26, further comprising the steps of: invoking a program to take an action relevant to the new instance, based on the query.
Claim 36
Dependent Claim
51 words
The program storage device of claim 26, wherein the case repository is a database, said method further comprising the steps of: said step of communicating data includes the step of communicating an ad hoc database query; and said retrieving step includes the step of retrieving information relevant to the database query.
Claim 37
Dependent Claim
135 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps of generating a case repository of instances for use in a knowledge system using case-based reasoning wherein the instances are structured as an ordered set of navigation elements stored in the case repository, comprising the method steps of: specifying one or more navigation elements corresponding to a new instance for input to the knowledge system, wherein a navigation element comprises an ordered triple including: a test expressing data navigation conditions; a text description explaining the navigation element; and a query; appending, responsive to said specifying step, the navigation element to the set of ordered navigation elements; and updating the case repository with the one or more navigation elements corresponding to the new instance.
Claim 38
Dependent Claim
135 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps of generating a case repository of instances for use in a knowledge system using case-based reasoning wherein the instances are structured as an ordered set of navigation elements stored in the case repository, comprising the method steps of: specifying one or more navigation elements corresponding to a new instance for input to the knowledge system, wherein a navigation element comprises an ordered triple including: a test expressing data navigation conditions; a text description explaining the navigation element; and a query; appending, responsive to said specifying step, the navigation element to the set of ordered navigation elements; and updating the case repository with the one or more navigation elements corresponding to the new instance.
References Cited (Backward Citations)
US5010478A
Cited
US4891766A
Cited
US4924408A
Cited
US4949278A
Cited
US5224206A
Cited
EP0442809A2
Cited
WO1992015951A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-02-09 | 2001-08-11 | 2002-02-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-02-09 | 2005-08-11 | 2006-02-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-02-09 | 2009-08-11 | 2010-02-10 | $7700.00 | Window Closed / Lapsed |