Similar information retrieval system and its method

• US 5,761,496 A
• Filed: 12/14/1994
• Issued: 06/02/1998
• Est. Priority Date: 12/14/1993
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Hattori, Masakazu
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Von Buhr, Maria N.
• Application Number:
  US08/355,971
• Time in Patent Office: 1,266 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 395/600, 395/603, 395/604, 395/605
• US Class Current: 707/796
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

The retrieval request input means 110 reads a retrieval request consisting of input keywords set up by the user as well as their importance degrees. The retrieval management section 120 causes the relation keyword generation section 121 and the retrieval expression generation section 122 to generate a retrieval expression by using background knowledge and retrieval parameters. The retrieval management section 120 causes the database management section to retrieve data from the database 160 based on a generated retrieval expression, causes the relation data acquisition section 124 to present a temporary retrieval result to the user, and causes the relevance database management section 123 to store user-instructed relation data into the relevance database 150. The retrieval management section 120 changes the retrieval parameters based on this relation data, causes the retrieval expression generation section 122 to generate a mew retrieval expression, and causes the database management section 125 to retrieve data again. The retrieval result output section 130 outputs the final retrieval result. Thus, this system allows the user to reflect his retrieval strategy and background knowledge about data easily and precisely and to execute similarity retrieval efficiently on a trial and error basis, without a substantial increase in the retrieval time.

Claims

1. An information retrieval system that retrieves from a database, on a trial and error basis, data satisfying a retrieval condition contained in a retrieval request issued by a user, said information retrieval system comprising:

a database management means for retrieving retrieval data from said database;

a retrieval request input means for accepting from a user a retrieval request including at least one input keyword and at least one degree of importance of the at least one input keyword;

a relation keyword generation means for generating at least one relation keyword using background knowledge and a retrieval parameter, the at least one relation keyword relating to the at least one input keyword;

a retrieval expression generation means for generating a retrieval expression using the at least one input keyword and the at least one relation keyword;

a retrieval management means for setting retrieval parameters to be used by said relation keyword generation means and for causing said database management means to retrieve the retrieval data based on the retrieval expression;

a retrieval result output means for outputting final retrieval results retrieved using said database management means;

a relation judgment information acquisition means for presenting a part of temporary retrieval results, retrieved using said database management means, to the user as retrieval data and for acquiring a retrieval processing stop instruction and relation judgment information from the user, wherein the relation judgment information acquisition means obtains relation judgment information from the user when the user is unsatisfied with the retrieval data presented by said relation judgment information acquisition means; and

a relation judgment information management means for storing and retrieving the relation judgment information,

wherein said retrieval management means further comprises;

means for modifying the retrieval parameters using the relation judgment information,

means for causing said relation keyword generation means to modify that at least one relation keyword,

means for causing said retrieval expression generation means to generate a new retrieval expression,

means for causing said database management means to retrieve new retrieval data based on the new retrieval expression when said retrieval data presentation means obtains relation judgment information from the user when the user is not satisfied with the retrieval data presented by said relation judgment information acquisition means, and

means for sending the retrieval data to said retrieval result output means as the final retrieval results when the user is satisfied with the retrieval data presented by said relation judgment information acquisition means as indicated by acquiring the retrieval processing stop instruction from the user.

2. An information retrieval system as claimed in claim 1, wherein said relation judgment information acquisition means comprises a relation data acquisition means for presenting the part of the temporary retrieval results, retrieved using said database management means, to the user as retrieval data;

and

means for obtaining relation data and instruction information for the relation data when the user judges that the retrieval data is relation data, and

wherein said relation judgment information management means further comprises means for storing and retrieving the relation data and the instruction information for the relation data.

3. An information retrieval system as claimed in claim 1, wherein said relation judgment information acquisition means comprises:

a non-relation data acquisition means for presenting the part of the temporary retrieval results, retrieved using said database management means, to the user as retrieval data; and

means for obtaining non-relation data and instruction information for the non-relation data when the user judges that the retrieval data is non-relation data, and

wherein said relation judgment information management means further comprises means for storing and retrieving the non-relation data and the instruction information for the non-relation data.

4. An information retrieval system as claimed in claim 1, wherein said relation judgment information acquisition means comprises:

a relation data acquisition means for presenting the part of the temporary retrieval results, retrieved using said database management means, to the user as retrieval data; and

means for obtaining relation data and instruction information for the relation data when the user judges that retrieval data is relation data,

a non-relation data acquisition means for presenting the part of the temporary retrieval results, retrieved using said database management means, to the user as retrieval data;

means for obtaining non-relation data and instruction information for the non-relation data when the user judges that retrieval data is non-relation data; and

wherein said relation judgment information management means further comprises means for storing and retrieving the relation data, the non-relation data, and the instruction information for the relation and non-relation data.

5. An information retrieval system as claimed in claim 1, wherein said relation keyword generation means further comprises means for performing a propagation operation using the at least one input keyword as initial propagation data;

and

means for generating the at least one relation keyword using one of the retrieval parameters as a threshold, wherein the one of the retrieval parameters was set up by said retrieval management means.

6. An information retrieval system as claimed in claim 5, wherein said background knowledge comprises an associative network including a plurality of keywords with links, each having a corresponding relation degree;

and

wherein said relation keyword generation means further comprises means for finding a relation degree between a first keyword and a second keyword by finding a maximum product of relation degrees of link strings connecting the first keyword and the second keyword wherein the first keyword matches one input keyword of the at least one input keyword entered from said retrieval request input means, and wherein the second keyword indirectly links to the first keyword; and

means for generating the at least one relation keyword using the second keyword if a product of a link between the first keyword and the second keyword and one of said at least one degree of importance of said one input keyword is at least as great as a value of one of the retrieval parameters set up by said retrieval management means.

7. An information retrieval system as claimed in claim 5, wherein said background knowledge comprises an associative network including a plurality of keywords with links, each having a corresponding relation degree;

and

wherein said relation keyword generation means further comprises means for finding a relation degree between a first keyword and a second keyword by finding a sum of products of relation degrees of link strings connecting the first keyword and the second keyword, wherein the first keyword matches one input keyword of the at least one input keyword entered from said retrieval request input means, and wherein the second keyword indirectly links to the first keyword; and

means for generating the at least one relation keyword using the second keyword if a product of a link between the first keyword and the second keyword and one of said at least one degree of importance of said one input keyword is at least as great as a value of one of the retrieval parameters set up by said retrieval management means.

8. An information retrieval system as claimed in claim 5, wherein said background knowledge comprises a conceptual hierarchy including a plurality of hierarchical keywords with links, each having a corresponding relation degree;

and

wherein said relation keyword generation means further comprises means for finding a relation degree between a first keyword and second keyword by finding a product of relation degrees of link strings from the first keyword to a third lowest-level keyword common to and higher than the first and second keywords, wherein the first keyword matches one input keyword of the at least one input keyword and wherein the second keyword indirectly links to the first keyword; and

means for generating the at least one relation keyword using the second keyword if a product of a link between the first keyword and the second keyword and one of said at least one degree of importance of said one input keyword is at least as great as a value of one of the retrieval parameters set up by said retrieval management means.

9. An information retrieval system that retrieves from a database, on a trial and error basis, data satisfying a retrieval condition contained in a retrieval request issued by a user, said information retrieval system comprising:

a database management means for retrieving retrieval data from said database;

a retrieval request input means for accepting from a user a retrieval request including at least one input keyword, at least one of importance of the at least one input keyword, and a retrieval result condition;

a relation keyword generation means for generating at least one relation keyword using background knowledge and a retrieval parameter, the at least one relation keyword relating to the at least one input keyword;

a retrieval expression generation means for generating a retrieval expression using the at least one input keyword and the at least one relation keyword;

a retrieval management means for setting retrieval parameters to be used by said relation keyword generation means and for causing said database management means to retrieve the retrieval data based on a retrieval expression obtained by said retrieval expression generation means; and

a retrieval result output means for outputting final retrieval results retrieved using said database management means;

wherein said retrieval management means further comprises;

means for modifying the retrieval parameters,

means for causing said relation keyword generation means to modify the at least one relation keyword,

means for causing said retrieval expression generation means to generate a new retrieval expression, and

means for causing said database management means to retreive data based on the new retrieval expression if a temporary result retrieved using said database management means does not satisfy the retrieval result condition obtained from said retrieval request input means, and

wherein said retrieval management means further comprises means for outputting a retrieval result as the final retrieval result when the temporary retrieval result satisfies the retrieval result condition.

10. An information retrieval means as claimed in claim 9, further comprising a retrieval count estimation means for estimating a retrieval count corresponding to the retrieval expression generated by said retrieval expression generation means.

11. An information retrieval system as claimed in claim 10, wherein said retrieval management means further comprises:

means for causing said retrieval expression generation means to generate the retrieval expression on a trial and error basis;

means for pre-processing by causing said retrieval count estimation means to estimate the retrieval count of the retrieval expression without causing said database management means to retrive data from said database and,

means for causing said retrieval expression generation means to generate the retrieval expression on a trial and error basis by causing said database management means to retrieve data from said database after the retrieval count estimation means has estimated the retrieval count.

12. An information retrieval system as claimed in claim 9, wherein said relation keyword generation means further comprises means for performing a propagation operation using the at least one input keyword as initial propagation data;

and

means for generating the at least one relation keyword using one of the retrieval parameters as a threshold, wherein the one of the retrieval parameters was set up by said retrieval management means.

13. An information retrieval system as claimed in claim 12, wherein said background knowledge comprises an associative network including a plurality of keywords with links, each having a corresponding relation degree;

and

wherein said relation keyword generation means further comprises means for finding a relation degree between a first keyword and a second keyword by finding a link maximum product of relation degrees of link strings connecting the first keyword and the second keyword, wherein the first keyword matches one of the at least one input keyword entered from said retrieval request input means, and wherein the second keyword indirectly links to the first keyword; and

means for generating the at least one relation keyword using the second keyword if a product of a link between the first keyword and the second keyword and one of said importance at least one of importance of the one of said at least one input keyword is at least as great as a value of one of the retrieval parameters set up by said retrieval management means.

14. An information retrieval system as claimed in claim 12, wherein said background knowledge comprises an associative network including a plurality of keywords with links, each having a corresponding relation degree;

and

wherein said relation keyword generation means further comprises means for finding a relation degree between a first keyword and a second keyword by finding a sum of products of relation degrees of link strings connecting the first keyword and the second keyword wherein the first keyword wherein the first keyword matches one of the at least one input keyword entered from said retrieval request input means, and wherein the second keyword indirectly links to the first keyword; and

means for generating the at least one relation keyword using the second keyword if a product of a link between the first keyword and the second keyword and one of said at least one degree of importance of the one of said at least one input keyword is at least as great as a value of one of the retrieval parameters set up by said retrieval management means.

15. An information retrieval system as claimed in claim 12, wherein said background knowledge comprises a conceptual hierarchy including a plurality of hierarchical keywords with links, each having a corresponding relation degree;

and

wherein said relation keyword generation means further comprises means for finding a relation degree between a first keyword and a second keyword by finding a product of relation degrees of link strings from the first keyword to a third lowest-level keyword common to and higher than the first and second keywords, wherein the first keyword matches one of the at least one input keyword entered from said retrieval request input means, and wherein the second keyword indirectly links to the first keyword; and

means for generating the at least one relation keyword using the second keyword if a product of a link between the first keyword and the second keyword and one of said at least one input keyword is at least as great as a value of one of the retrieval parameters set up by said retrieval management means.

16. An information retrieval method that retrieves from a database, on a trial and error basis, data satisfying a retrieval condition contained in a retrieval request issued by a user, said information retrieval method comprising the steps of:

accepting a retrieval request including at least one input keyword and at least one degree of importance of the at least one input keyword from the user;

generating at least one relation keyword, related to said at least one input keyword, using background knowledge and a retrieval parameter;

generating a retrieval expression using said at least one input keyword and said at least one relation keyword;

retrieving data from said database based on said retrieval expression;

presenting a part of a temporary retrieval result, obtained in said retrieving step, to the user as retrieval data;

acquiring one of a retrieval processing stop instruction and data relation judgment information from the user;

modifying said retrieval parameter using said data relation judgment information and returning to said step of generating at least one relation keyword if the acquiring step acquires said data relation judgment information from the user; and

outputting said temporary retrieval result as said retrieval result when said acquiring step acquires said retrieval processing stop instruction.

17. An information retrieval method as claimed in claim 16, wherein said acquiring step comprises the sub-steps of:

presenting the part of said temporary retrieval results, obtained in said retrieving step, to the user as retrieval data;

determining if the user judges that said retrieval data is relation data;

obtaining relation data and corresponding instruction information when the user judges said retrieval data is relation data; and

storing said relation data and instruction information in a relevance database when the user judges said retrieval data is relation data.

18. An information retrieval method as claimed in claim 16, wherein said acquiring step comprises the sub-steps of:

presenting the part of said temporary retrieval results, obtained in said retrieving step, to the user as retrieval data;

determining if the user judges that said retrieval data is non-relation data;

obtaining non-relation data and corresponding instruction information when the user judges said retrieval data is non-relation data; and

storing said non-relation data and instruction information in a relevance database when the user judges said retrieval data is non-relation data.

19. An information retrieval method as claimed in claim 16, wherein said acquiring step comprises the sub-steps of:

presenting the part of said temporary retrieval results, obtained in said retrieving step, to the user as retrieval data;

determining if the user judges that the retrieval data is relation data;

obtaining the relation data and corresponding instruction information when the user judges that the retrieval data is relation data;

storing the relation data and the corresponding instruction information in a relevance database when the user judges that the retrieval data is relation data;

obtaining the non-relation data and corresponding instruction information when the user judges that the retrieval data is non-relation data;

storing the non-relation data and the corresponding instruction information in a relevance database when the user judges that the retrieval data is non-relation data.

20. An information retrieval method as claimed in claim 16, wherein said step of generating at least one relation keyword comprises the sub-steps of:

performing a propagation operation using said at least one input keyword as initial propagation data, and

generating the at least one relation using said retrieval parameter as a threshold.

21. An information retrieval method as claimed in claim 20, wherein said step of generating the at least one relation keyword comprises the sub-steps of:

generating as said background knowledge an associative network including a plurality of keywords with links, each having a corresponding relation degree;

finding a relation degree between a first keyword and a second keyword by finding a maximum product of relation degrees of link strings connecting the first keyword and the second keyword, wherein the first keyword matches one input keyword of the at least one input keyword and wherein the second keyword indirectly links to said first keyword, and

generating a relation keyword using the second keyword if a product of a link between the first keyword and the second keyword and said at least one degree of importance of said at least one input keyword is at least as great as said retrieval parameter.

22. An information retrieval method as claimed in claim 20, wherein said step of generating at least one relation keyword comprises the sub-steps of:

generating as said background knowledge an associative network including a plurality of keywords with links, each having a corresponding relation degree;

finding a relation degree between a first keyword and a second keyword by finding a maximum product of relation degrees of link strings connecting the first keyword and the second keyword, wherein the first keyword matches one input keyword of the at least one input keyword and wherein the second keyword indirectly links to said first keyword if a product of a link between the first keyword and the second keyword and said at least one degree of importance of said at least one input keyword is at least as great as said retrieval parameter.

23. An information retrieval method as claimed in claim 20, wherein said step of generating at least one relation keyword comprises the sub-steps of:

generating as said background knowledge a conceptual hierarchy including a plurality of hierarchical keywords with links, each having a corresponding relation degree;

finding a relation degree between a first keyword and a second keyword indirectly linked to said first keyword by finding a product of the relation degrees of the link strings from the first keyword to a third lowest-level keyword common to and higher than the first keyword and the second keyword; and

generating the at least one relation keyword using the second keyword if a product of a link between the first keyword and the second keyword and said at least one degree of importance of said first keyword is at least as large as said retrieval parameter.

24. An information retrieval method that retrieves from a database, on a trial and error basis, data satisfying a retrieval result condition contained in a retrieval request issued by a user, said information retrieval method comprising the steps of:

accepting a retrieval request including at least one input keyword and at least one degree of importance of the at least one input keyword from the user;

generating the at least one relation keyword, related to said at least one input keyword, using background knowledge and a retrieval parameter;

generating a retrieval expression using said at least one input keyword and said at least one relation keyword;

retrieving a temporary retrieval result from said database based on said retrieval expression;

modifying said retrieval parameter and returning to said step of generating at least one relation keyword if the temporary retrieval result obtained in said retrieving step does not satisfy said retrieval result condition; and

outputting the temporary retrieval result as a final result if the temporary retrieval result obtained in said retrieving step satisfies said retrieval result condition.

25. An information retrieval method as claimed in claim 24, wherein said retrieving step estimates a retrieval count corresponding to a generated retrieval expression.

26. An information retrieval method as claimed in claim 25, wherein said step of generating the retrieval expression comprises the sub-steps of:

generating a retrieval expression on a trial and error basis;

pre-processing by estimating a retrieval count for the retrieval expression generated in the generating sub-step; and

,

after the sub-steps of generating and pre-processing, generating a retrieval expression on a trial and error basis while performing said retrieving step.

27. An information retrieval method as claimed in claim 24, wherein said generating step comprises the sub-steps of:

performing a propagation operation using said at least one input keyword as initial propagation data, and

generating the at least one relation keyword using said retrieval parameter as a threshold.

28. An information retrieval method as claimed in claim 27, wherein said step of generating at least the relation keyword comprises the sub-steps of:

generating as said background knowledge an associative network including a plurality of keywords with links, each having a corresponding relation degree;

finding a relation degree between a first keyword and a second keyword by finding a maximum product of relation degrees of link strings connecting the first keyword and the second keyword, wherein the first keyword matches one of input keyword the at least one input keyword and wherein the second keyword indirectly links to said first keyword, and

generating one relation keyword of the at least one relation keyword using the second keyword if a product of a link between the first keyword and the second keyword and said degree of importance of said at least one input keyword is at least as great as said retrieval parameter.

29. An information retrieval method as claimed in claim 27, wherein said step of generating at least one relation keyword comprises the sub-steps of:

generating as said background knowledge an associative network including a plurality of keywords with links, each having a corresponding relation degree;

finding a relation degree between a first keyword and a second keyword by finding a maximum product of relation degrees of link strings connecting the first keyword and the second keyword, wherein the first keyword matches one input keyword of the at least one input keyword and wherein the second keyword indirectly links to said first keyword if a product of a link between the first keyword and the second keyword and said at least one degree of importance of said at least one input keyword is at least as great as said retrieval parameter.

30. An information retrieval method as claimed in claim 27, wherein said step of generating at least one relation keyword comprises the sub-steps of:

generating as said background knowledge a conceptual hierarchy including a plurality of hierarchical keywords with links, each having a corresponding relation degree;

finding a relation degree between a first keyword and a second keyword indirectly linked to said first keyword by finding a product of the relation degrees of the link strings from the first keyword to a third lowest-level keyword common to and higher than the first keyword and the second keyword; and

generating one relation keyword of the at least one relation keyword using the second keyword if a product of a link between the first keyword and the second keyword and said at least one degree of importance of said first keyword is at least as large as said retrieval parameter.

31. An information retrieval system that retrieves data satisfying a retrieval condition from a database, said information retrieval system comprising:

a database management means for managing the database;

a retrieval request input means for accepting a retrieval request including at least one input keyword and at least one degree of importance corresponding to the at least one input keyword;

a relation keyword generation means for generating at least one relation keyword based on background knowledge and a retrieval parameter, the at least one relation keyword relating to the at least one input keyword;

a retrieval expression generation means for generating a retrieval expression based on the at least one input keyword and the at least one relation keyword;

a retrieval means for retrieving retrieval data based on the retrieval expression from said database and for presenting a retrieval result to a user;

a retrieval result output means for outputting the retrieval result; and

a relation judgment information acquisition means for acquiring relation judgment information based on the retrieval result from the user,

wherein said retrieval means further comprises;

means for modifying the retrieval parameter based on the relation judgment information,

means for causing said relation keyword generation means to modify the at least one relation keyword,

means for causing said retrieval expression generation means to generate a new retrieval expression,

means for retrieving new retrieval data based on the new retrieval expression, and

means for sending the retrieval result to said retrieval result output means when said relation judgment information acquisition means does not acquire the relation judgment information.

32. An information retrieval system that retrieves data satisfying a retrieval condition from a database, said information retrieval system comprising:

a database management means for managing the database;

a retrieval request input means for accepting a retrieval request condition and a retrieval request including at least one input keyword and at least one degree of importance corresponding to the at least one input keyword;

a relation keyword generation means for generating at least one relation keyword based on background knowledge and a retrieval parameter, the relation keyword relating to the at least one input keyword;

a retrieval expression generation means for generating a retrieval expression based on the at least one input keyword and the at least one relation keyword;

a retrieval means for retrieving retrieval data based on the retrieval expression from said database; and

a retrieval result output means for outputting a retrieval result retrieved using said retrieval means, wherein said retrieval means further comprises;

means for modifying the retrieval parameter if the retrieval result does not satisfy the retrieval result condition,

means for causing said relation keyword generation means to modify the at least one relation keyword,

means for causing said retrieval expression generation means to generate a new retrieval expression,

means for retrieving new retrieval data based on the new retrieval expression, and

means for sending the retrieval result to said retrieval result output means when the retrieval result satisfies the retrieval result condition.

33. An information retrieval method that retrieves data satisfying a retrieval condition from a database, said information retrieval method comprising the steps of:

accepting a retrieval result including at least one input keyword and at least one degree of importance corresponding to the at least one input keyword;

generating at least one relation keyword based on background knowledge and a retrieval parameter, the at least one relation keyword relating to the at least one input keyword;

generating a retrieval expression based on the at least one input keyword and the at least one relation keyword;

retrieving retrieval data based on the retrieval expression from said database;

presenting a retrieval result obtained in the retrieving step to a user;

acquiring from the user relation judgment information based on the retrieval result;

modifying the retrieval parameter based on the relation judgment information and returning to said step of generating at least one relation keyword if the acquiring step acquires the relation judgment information from the user; and

outputting the retrieval result when said acquiring step does not acquire the relation judgment information from the user.

34. An information retrieval method that retrieves data satisfying a retrieval condition from a database, said information retrieval method comprising the steps of:

accepting a retrieval result condition and a retrieval request including at least one input keyword and at least one degree of importance corresponding to the at least one input keyword;

generating at least one relation keyword based on background knowledge and a retrieval parameter, the at least one relation keyword relating to the at least one input keyword;

generating a retrieval expression based on the at least one input keyword and the at least one relation keyword;

retrieving retrieval data based on the retrieval expression from said database;

modifying the retrieval parameter based on the relation judgment information and returning to said step of generating at least one relation keyword if a retrieval result obtained in said retrieving step does not satisfy the retrieval result condition; and

outputting the retrieval result when a retrieval result obtained in said retrieving step satisfies the retrieval result condition.