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.

Download full text files

Export metadata

Additional Services

Search Google Scholar
Metadaten
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