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.

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Klaus-Dieter Althoff, Stefan Wess, Guido Derwand
URN (permanent link):urn:nbn:de:hbz:386-kluedo-1210
Document Type:Preprint
Language of publication:English
Year of Completion:1991
Year of Publication:1991
Publishing Institute:Technische Universität Kaiserslautern
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:Fachbereich Informatik
DDC-Cassification:004 Datenverarbeitung; Informatik

$Rev: 12793 $