Typical question-answering systems accept questions of the types who, when, where, what, and how. The response is generated as the result of a search applied to a document base. Because this document collection may include documents from the Web, not all of the documents can be preprocessed.

The system retrieves sentences from the document base using keywords derived from the question. The system must then be able to evaluate these sentences, and offer the best ones as potential answers. This paper describes such a system, for Japanese language questions, with answers derived from documents in Japanese.

The score for a retrieved sentence, or sentence chain, when a number of found sentences must be combined to cover all of the keywords in the question, is ranked based on the sum of four subscores. These are, in order (for the order turns out to be important), the matching score in terms of 2-grams, the matching score in terms of keywords, a matching score based on dependency relations in a form of parse tree, and the matching in terms of question type. Note that these values are progressively more expensive to compute. The novelty in this paper is the use of an A* algorithm to find the best answers. This is possible because, except for the last evaluator, one can find approximate over-estimators for each of the evaluations. The required search structure is obtained by considering the evaluation to have a tree-based structure, with the levels corresponding to the successive evaluators taken in the order given above.

The paper includes the results of tests of the system from a workshop on Japanese question-answering systems. These results show that the system achieved better results than other pruning-based systems. Two of the evaluations seem to depend on the language being Japanese, namely, the use of 2-grams and the dependency metric. It would be interesting to see to what extent the methods can be transferred to other languages. The paper is highly recommended to those interested in question-answering systems.