This invention relates to the subject matter identified in the title. An effective interaction is conducted by giving the user adequate information during information search so as to improve the search efficiency and accuracy. A CPU initially sets a set G containing deleted solution candidates to null and receives input for a search question Q from the user (S1). The CPU refers to a database storage section and creates a solution candidate set F as the result of the search of the database (D) in response to the search question Q by using the similarity of labels defined by a thesaurus T or a subset R of the thesaurus T (S2). The CPU presents the user the information concerning the solution candidates and search question Q as the help for interaction on a display part (S3). The user can check if there is a solution among the solution candidates.