Indexing role hierarchies for words in a search index

• US 8,229,730 B2
• Filed: 08/29/2008
• Issued: 07/24/2012
• Est. Priority Date: 08/31/2007
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Van Den Berg, Martin H., Thione, Giovanni L., Walters, Chad P., Crouch, Richard S.
• Primary Examiner(s): NGUYEN, KIM T
• Application Number:
  US12/201,721
• Publication Number:
  US 20090063473A1
• Time in Patent Office: 1,425 Days
• Field of Search: 704/4, 704/9
• US Class Current: 704/4
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Methods, systems and computer readable media for finding documents in a data store that match a natural language query submitted by a user are provided. The documents and queries are matched by determining that words within the query have the same relationship to each other as the same words in the document. Documents are semantically analyzed and words in the document are indexed along with the role the word plays in a sentence. The initial semantic role may be generalized using a role hierarchy and stored in the index along with the original role. A similar analysis may be used with the search query to find words used in the same role in both the query and the document.

Claims

1. One or more computer-readable media having computer-executable instructions embodied thereon for performing a method of expanding and indexing relationships between words within a sentence, the method comprising:

receiving a first electronic document having content that includes text;

breaking the text into one or more sentences;

determining a first grammatical role for a word in the sentence;

determining that the word has more than one potential grammatical role;

assigning a second grammatical role to the word, wherein the second grammatical role is a subservient grammatical role to the first grammatical role, which is a dominant grammatical role, wherein the subservient grammatical role fits within a definition of the dominant grammatical role and has a more specific definition; and

storing the word with the first grammatical role and the second grammatical role in an index that associates the word and the sentence with the first electronic document, thereby allowing a search engine to match the first electronic document with a search query that includes similar words having similar roles.

2. The media of claim 1, wherein the method further comprises:

receiving the search query containing the word;

determining that the word is used in the first grammatical role within the search query;

determining that the word has more than one potential grammatical role within the search query; and

assigning a third grammatical role to the word.

3. The media of claim 2, wherein the method further comprises:

searching the index to find one or more electronic documents having the word used in one or more of the first grammatical role and the third grammatical role;

determining the first electronic document is a first match to the search query;

determining a second electronic document having the word assigned to the first grammatical role and the third grammatical role is a second match to the search query; and

ranking the second electronic document as a better match to the search query than the first electronic document because the second electronic document has the word in the same roles that are assigned to the word in the search query.

4. The media of claim 2, wherein the method further comprises:

determining that at least two documents associated with entries in the index contain the word associated with the first grammatical role or the third grammatical role; and

assigning a higher ranking to documents that contain the word associated with more of the same roles assigned to the word in the search query.

5. The media of claim 1, wherein the second grammatical role is assigned using a role hierarchy, wherein the role hierarchy includes a hierarchy of grammatical roles including a root role that is general and at least one level of sub roles that are more specific than the root role.

6. The media of claim 1, wherein storing the word with the first grammatical role and the second grammatical role includes creating a first term in the index including the word and the first grammatical role and a second term in the index including the word and the second grammatical role.

7. The media of claim 1, wherein the first grammatical role is initiator and the second grammatical role includes one or more of effector and agent.

8. A method for matching a search query to text within a one or more documents comprising:

receiving a natural language search query containing a plurality of words;

assigning a primary grammatical role to a word in the search query;

assigning an additional grammatical role to the word from the search query using a role hierarchy that defines a grammatical relationship between the primary grammatical role and the additional grammatical role, wherein grammatical roles within the role hierarchy get more specific the further grammatical roles are from a root grammatical role, and wherein the additional grammatical role fits within a definition of the primary grammatical role and has a more specific definition, wherein the additional grammatical role is a subservient grammatical role to the primary grammatical role, which is a dominant grammatical role; and

determining, at a computing device, that at least one document referenced in an index, which associates the word and a sentence within the at least one document with one or more grammatical roles, includes the word from the search query assigned to one or more of the primary grammatical role and the additional grammatical role.

9. The method of claim 8 further comprising presenting information describing the at least one document.

10. The method of claim 8, further comprising generating additional words to search the index by adding at least one of a synonym and a hypernym for one or more words in the search query to a list of search terms, wherein a search term includes a single word and an associated role, and wherein the synonym and the hypernym form search terms with the roles assigned to the one or more words for which the synonym and the hypernym are synonyms and hypernyms.

11. The method of claim 8, further comprising ranking the one or more documents, wherein a higher ranking is given when the word in the search query that is assigned more than one role has multiple roles in common with the word occurring in the index.

12. The method of claim 8, further comprising:

receiving a sentence that is part of a document;

assigning a primary role for words in the sentence;

assigning at least one additional role to at least one word in the sentence having the primary role using the role hierarchy; and

storing the words in the sentence with the at least one role assigned to the words in the sentence in the index that associates the words in the sentence and the sentence with the document.

13. The method of claim 12, further comprising indexing the words and the roles in a term that includes a single word and an assigned role, wherein each term includes one word and one role.

14. The method of claim 8, wherein the primary role is when and the additional role is one or more of before, at, and after.

15. One or more computer-storage media having computer-executable instructions embodied thereon for performing a method of indexing document contents using a role hierarchy, the method comprising:

receiving a first electronic document having content that includes text;

identifying a sentence that is part of the first electronic document;

assigning a first grammatical role to a word in the sentence;

determining that the word has more than one potential grammatical role;

assigning at least a second grammatical role to the word using the role hierarchy, which includes a hierarchy of grammatical roles including a root role that is general and at least one level of sub roles that are more specific than the root role, wherein the second grammatical role is a subservient grammatical role to the first grammatical role, which is a dominant grammatical role, and fits within a definition of the dominant grammatical role and has a more specific definition; and

storing the word with the first grammatical role and the second grammatical role in an index that associates the words and the sentence with the electronic document, thereby allowing a search engine to match the first electronic document with a search query that includes similar words having similar roles.

16. The media of claim 15, wherein storing the word and the roles includes generating a term that includes the word and an assigned role, wherein each term includes one word and one role.

17. The media of claim 15, wherein storing the word and the roles includes generating a term that includes the word and an assigned role, wherein each term includes one word and multiple roles.

18. The media of claim 15, wherein the method further comprises:

receiving a natural language search query containing a plurality of words;

assigning a primary grammatical role to the words in the plurality of words;

assigning at least one additional grammatical role to at least one word in the plurality of words using the role hierarchy; and

determining that one or more documents referenced in the index have at least one word in the plurality of words assigned one or more of the same roles.

19. The media of claim 18, wherein the method further comprises:

ranking the one or more documents, wherein documents with more matching words and the roles are given a higher rank, and wherein more ranking points are given to a word in the plurality of words that is associated with multiple roles has more roles in common with an occurrence of the word in the index.

20. The media of claim 19, wherein the method further includes displaying the one or more documents according to a rank assigned to each of the one or more documents.