Incremental iterative retrieval and browsing for efficient conversational CBR systems

A case base is a repository of past experiences that can be used for proble m solving. Given a new problem, expressed in the form of a query, the case base is browsed in search of "similar" or "relevant" cases. Conversational case-based reasoning (CBR) systems generally support user interaction durin g case retrieval and adaptation. Here we focus on case retrieval where user s initiate problem solving by entering a partial problem description. Durin g an interactive CBR session, a user may submit additional queries to provi de a "focus of attention". These queries may be obtained by relaxing or res tricting the constraints specified for a prior query. Thus, case retrieval involves the iterative evaluation of a series of queries against the case b ase, where each query in the series is obtained by restricting or relaxing the preceding query. This paper considers alternative approaches for implementing iterative brow sing in conversational CBR systems. First, we discuss a naive algorithm, wh ich evaluates each query independent of earlier evaluations. Second, we int roduce an incremental algorithm, which reuses the results of past query eva luations to minimize the computation required for subsequent queries. In pa rticular, the paper proposes an efficient algorithm for case base browsing and retrieval using database techniques for incremental view maintenance. I n addition, the paper evaluates scalability of the proposed algorithm using its performance model. The model is created using algorithmic complexity a nd experimental evaluation of the system performance.