Using k-d Trees to Improve the Retrieval Step in Case-Based Reasoning?
- Retrieval of cases is one important step within the case-based reasoning paradigm. We propose an improvement of this stage in the process model for finding most similar cases with an average effort of O[log2n], n number of cases. The basic idea of the algorithm is to use the heterogeneity of the search space for a density-based structuring and to employ this precomputed structure, a k-d tree, for efficient case retrieval according to a given similarity measure sim. In addition to illustrating the basic idea, we present the expe- rimental results of a comparison of four different k-d tree generating strategies as well as introduce the notion of virtual bounds as a new one that significantly reduces the retrieval effort from a more pragmatic perspective. The presented approach is fully implemented within the (Patdex) system, a case-based reasoning system for diagnostic applications in engineering domains.
Author: | Klaus-Dieter Althoff, Stefan Wess, Guido Derwand |
---|---|
URN: | urn:nbn:de:hbz:386-kluedo-1210 |
Document Type: | Preprint |
Language of publication: | English |
Year of Completion: | 1991 |
Year of first Publication: | 1991 |
Publishing Institution: | Technische Universität Kaiserslautern |
Date of the Publication (Server): | 2000/04/03 |
Tag: | Case-Based Reasoning; Fallbasiertes Schliessen |
Note: | Funding for this research has been partially provided by the Commission of the European Communities (Esprit contract P6322, the InReCa project). |
Faculties / Organisational entities: | Kaiserslautern - Fachbereich Informatik |
DDC-Cassification: | 0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik |
Licence (German): | Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011 |