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 (permanent link):||urn:nbn:de:hbz:386-kluedo-1210|
|Language of publication:||English|
|Year of Completion:||1991|
|Year of Publication:||1991|
|Publishing Institute:||Technische Universität Kaiserslautern|
|Date of the Publication (Server):||2000/04/03|
|Tag:||Case-Based Reasoning; Fallbasiertes Schliessen|
Funding for this research has been partially provided by the Commission of the European Communities (Esprit contract P6322, the InReCa project).
|Faculties / Organisational entities:||Fachbereich Informatik|
|DDC-Cassification:||0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik|
|Licence (German):||Standard gemäß KLUEDO-Leitlinien vor dem 27.05.2011|