System for improving the performance of information retrieval-type tasks by identifying the relations of constituents

• US 6,901,402 B1
• Filed: 06/18/1999
• Issued: 05/31/2005
• Est. Priority Date: 06/18/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Suzuki, Hisami, Corston-Oliver, Simon H., Dolan, William B.
• Primary Examiner(s): PARDO, THUY N
• Application Number:
  US09/336,200
• Time in Patent Office: 2,174 Days
• Field of Search: 707/5, 707/102, 707/103, 707/104, 707/101, 707/4, 707/1, 704/9, 395/813
• US Class Current: 1/1
• CPC Class Codes: B42D 15/00 Printed matter of special format or style not otherwise provided for
• CPC Class Codes: B42D 15/0053 Forms specially designed for commercial use, e.g. bills, receipts, offer or order sheets, coupons
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• 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
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system is utilized for determining a relationship between first and second textual inputs. The system identifies constituents in the first textual input, having predetermined characteristics indicative of usefulness in determining the relationship. The relationship is then determined based on the constituents identified. The constituents can be eliminated from the first textual input, weighted in the first textual input, or simply annotated in one of a variety of ways.

Claims

1. A method of determining a relationship between first and second textual inputs, the method comprising:

obtaining a set of relations, the relations including grammatical relations or case;

identifying constituents in the first textual input that have the relations; and

determining the relationship between the first and second textual inputs based on the constituents identified.

2. The method of claim 1 wherein the determining step includes:

determining the relationship between the first and second textual inputs based on the relations.

3. The method of claim 1 wherein obtaining a set of relations comprises:

obtaining a hierarchy of grammatical relations; and

obtaining a hierarchy threshold based on a usefulness of grammatical relations in the hierarchy in determining the relationship between the first and second textual inputs.

4. The method of claim 3 wherein the determining step comprises:

determining the usefulness of identified constituents by locating the grammatical relations associated with the identified constituents in the hierarchy.

5. The method of claim 4 wherein the identifying step comprises:

identifying low ranked constituents having corresponding grammatical relations located in the hierarchy below the hierarchy threshold.

6. The method of claim 5 wherein the determining step comprises:

determining the relationship based on constituents in the first textual input, other than the low ranked constituents.

7. The method of claim 5 wherein the identifying step includes:

identifying high ranked constituents having a corresponding grammatical relation located in the hierarchy at least as high as the hierarchy threshold; and

annotating the high-ranked constituents with a weighting value which weights the high-ranked constituents higher than low-ranked constituents.

8. The method of claim 7 wherein identifying constituents in the first textual input comprises:

annotating the high-ranked and low-ranked constituents with fine values based on a location of grammatical relations corresponding to each of the constituents in the hierarchy, the fine values being indicative of relative usefulness of the constituents in determining the relationship.

9. The method of claim 8 wherein the step of determining the relationship based on the constituents comprises:

determining the relationship based on the fine values associated with constituents.

10. The method of claim 4 wherein the determining step comprises:

preferentially matching terms in the first textual input against higher constituents in the second textual input having corresponding grammatical relations located relatively higher on the hierarchy than grammatical relations corresponding to lower constituents.

11. The method of claim 10 wherein the first textual input comprises a document and the second textual input comprises an information retrieval query and wherein preferentially matching comprises:

obtaining an index having entries corresponding to the document, the entries corresponding to only the higher constituents as opposed to the lower constituents; and

matching search terms in the query against the entries in the index.

12. The method of claim 10 wherein the first textual input comprises a document and the second textual input comprises an information retrieval query and wherein preferentially matching comprises:

obtaining an index having entries corresponding to the document, the entries corresponding to the higher constituents having higher weighting values associated therewith and the entries corresponding to the lower constituents having lower weighting values associated therewith; and

matching search terms in the query against the entries in the index based on the higher and lower weighting values.

13. The method of claim 1 wherein obtaining relations comprises:

obtaining a hierarchy of case information; and

obtaining a hierarchy threshold based on the usefulness of a constituent having that case.

14. The method of claim 13 wherein the determining step comprises:

determining the usefulness of the identified constituents by locating the case information associated with the identified constituents in the hierarchy.

15. The method of claim 14 wherein the identifying step comprises:

identifying low ranked constituents having the case indicated by the case information.

16. The method of claim 15 wherein determining the relationship between the first and second textual inputs comprises:

determining the relationship based on constituents in the first textual input, other than the low ranked constituents.

17. The method of claim 15 wherein the identifying step includes:

identifying high ranked constituents having corresponding case information located in the hierarchy at least as high as the hierarchy threshold; and

annotating the lower ranked constituents with a weighting value which weights the low ranked constituents lower than the high ranked constituents.

18. The method of claim 17 wherein identifying constituents in the first textual input comprises:

annotating the low ranked and high ranked constituents with fine values based on a location of the case information associated with each of the low ranked and high ranked constituents in the hierarchy, the fine values being indicative of relative usefulness of the constituents.

19. The method of claim 18 wherein the step of determining the relationship based on the constituents comprises:

determining the relationship based on the fine values associated with the constituents.

20. The method of claim 14 wherein the determining step comprises:

preferentially matching terms in the first textual input against higher ranked constituents in the second textual input having corresponding grammatical relations located relatively higher on the hierarchy than grammatical relations corresponding to lower constituents.

21. The method of claim 20 wherein the first textual input comprises a document and the second textual input comprises an information retrieval query and wherein preferentially matching comprises:

obtaining an index having entries corresponding to the document, the entries corresponding to only the higher ranked constituents as opposed to the lower ranked constituents; and

matching the search terms in the query against the entries in the index.

22. The method of claim 20 wherein the first textual input comprises a document and the second textual input comprises an information retrieval query and wherein preferentially matching comprises:

obtaining an index having entries corresponding to the document, the entries corresponding to the higher ranked constituents having higher weighting values associated therewith and the entries corresponding to the lower ranked constituents having lower weighting values associated therewith; and

matching the search terms in the query against the entries in the index based on the higher and lower weighting values.

33. The method of claim 1 wherein obtaining a set of relations comprises:

obtaining case information based on the usefulness of a constituent having that case; and

obtaining grammatical relation information based on a usefulness of a constituent having that grammatical relation.

37. The method of claim 33 wherein determining the relationship comprises:

determining the usefulness of the identified constituents based on the case information and the grammatical relation information.

38. The method of claim 37 wherein obtaining case information comprises:

obtaining a hierarchy of case information; and

obtaining a case hierarchy threshold based on the usefulness of a constituent having that case.

39. The method of claim 38 wherein obtaining grammatical relation information comprises:

obtaining a hierarchy of grammatical relations; and

obtaining a hierarchy threshold based on a usefulness of grammatical relations in the hierarchy in determining the relationship between the first and second textual inputs.

23. A method of determining a relationship between first and second textual inputs, the method comprising:

analyzing the first textual input to obtain relations of constituents thereof;

determining a relative importance of the constituents in determining the relationship between the first and second textual inputs based on the relations obtained; and

determining the relationship between the first and second textual inputs based on the constituents and the relative importance of the constituents.

24. The method of claim 23 and further comprising:

obtaining a threshold importance and wherein determining the relationship comprises determining the relationship based only on constituents having a relative importance above the threshold importance.

25. The method of claim 23 and further comprising:

assigning a weighting value to each constituent based on the relative importance corresponding to each constituent, and wherein determining the relationship comprises determining the relationship based on the weighting values associated with the constituents.

26. The method of claim 23 wherein the first textual input comprises a document and the second textual input comprises a query and wherein determining the relationship between the first and second textual inputs comprises determining similarity in meaning between the document and the query.

27. The method of claim 23 wherein the first and second textual inputs each comprise documents and wherein determining the relationship comprises determining a similarity in meaning between the documents.

28. The method of claim 27 wherein determining the relationship further comprises determining whether the first and second textual inputs are to be clustered in a logical cluster based on the similarity in meaning between the first and second documents.

29. The method of claim 23 wherein the analyzing step comprises:

obtaining case information corresponding to the constituents in the first textual input.

30. The method of claim 29 wherein determining a relative importance comprises:

determining a relative importance of the constituents based on the corresponding case information.

31. The method of claim 23 wherein the analyzing step comprises:

obtaining grammatical relations corresponding to the constituents in the first textual input.

32. The method of claim 31 wherein determining a relative importance comprises:

determining a relative importance of the constituents based on the corresponding grammatical relations.

34. A computer readable medium storing a data structure used in determining a relationship between first and second textual inputs, the data structure comprising:

a plurality of pre-computed aspects of at least one of the first and second textual inputs, the pre-computed aspects being useful in determining the relationship between the first and second textual inputs;

wherein the plurality of pre-computed aspects includes a linguistic analysis of at least a portion of the first and second textual inputs.

35. The computer readable medium of claim 34 wherein the plurality of pre-computed aspects include:

a plurality of constituents of the first or second textual input; and

a predetermined indication of usefulness, associated with the plurality of constituents, in determining the relationship between the first and second textual inputs.

36. A method of determining a relationship between first and second textual inputs, the method comprising:

obtaining a hierarchy of relations;

obtaining a hierarchy threshold based on a usefulness of the relations in the hierarchy in determining the relationship between the first and second textual inputs;

identifying constituents in the first textual input that have the relations in the hierarchy;

determining a usefulness of the identified constituents by locating the identified constituents in the hierarchy; and

determining the relationship between the first and second textual inputs based on identified constituents having associated relations above the hierarchy threshold.