Finding related entity results for search queries

• US 8,195,655 B2
• Filed: 06/05/2007
• Issued: 06/05/2012
• Est. Priority Date: 06/05/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Agrawal, Sanjay, Chakrabarti, Kaushik, Chaudhuri, Surajit, Ganti, Venkatesh
• Primary Examiner(s): Ali, Mohammad
• Assistant Examiner(s): WILLIS, AMANDA LYNN
• Application Number:
  US11/758,024
• Publication Number:
  US 20080306908A1
• Time in Patent Office: 1,827 Days
• Field of Search: 707/741, 707/748, 707723-730, 707999004-999007, 707/999.003
• US Class Current: 707/730
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

Architecture for finding related entities for web search queries. An extraction component takes a document as input and outputs all the mentions (or occurrences) of named entities such as names of people, organizations, locations, and products in the document, as well as entity metadata. An indexing component takes a document identifier (docID) and the set of mentions of named entities and, stores and indexes the information for retrieval. A document-based search component takes a keyword query and returns the docIDs of the top documents matching with the query. A retrieval component takes a docID as input, accesses the information stored by the indexing component and returns the set of mentions of named entities in the document. This information is then passed to an entity scoring and thresholding component that computes an aggregate score of each entity and selects the entities to return to the user.

Claims

1. A computer-implemented search system, comprising:

an extraction component configured to extract named entities from documents having corresponding document identifiers;

an indexing component configured to create and store;

a document index that indexes the named entities by the document identifiers to indicate whether the named entities occur in the documents; and

an inverted index that indexes the document identifiers by word identifiers of words that occur in the documents, wherein the document index and the inverted index are at least partly created in advance of receiving a keyword query from a user;

a document-based search component configured to;

receive the keyword query from the user, the keyword query comprising keywords; and

provide the keywords to the inverted index to identify individual document identifiers corresponding to individual matching documents that match one or more of the keywords of the keyword query;

a retrieval component configured to;

retrieve direct matching document entities that directly match at least one of the keywords of the keyword query; and

provide the individual document identifiers to the document index and retrieve co-occurring related named entities from the document index, wherein the co-occurring related named entities do not directly match the keywords of the keyword query but occur in the individual matching documents with the direct matching document entities; and

a scoring component configured to;

compute aggregate relevance scores for the co-occurring related named entities that occur in the individual matching documents; and

return one or more of the co-occurring related named entities in response to the keyword query based on the aggregate relevance scores; and

at least one processing unit configured to execute one or more of the extraction component, the indexing component, the document-based search component, the retrieval component, or the scoring component.

2. The system of claim 1, wherein the returned one or more co-occurring related named entities are selected based upon one or more of:

a number of co-occurrences or positional proximity to an individual direct matching document entity.

3. The system of claim 1, wherein the named entities are associated with at least one of an entity type or entity position in the documents.

4. The system of claim 1, wherein the document-based search component is configured to return the individual document identifiers corresponding to the individual matching documents according to rank.

5. The system of claim 4, wherein the retrieval component is configured to retrieve a number of the co-occurring related named entities in the returned individual matching documents.

6. The system of claim 5, wherein the scoring component is further configured to compute the aggregate relevance score for the co-occurring related named entities based on the number of co-occurrences.

7. The system of claim 1, further comprising a machine learning and reasoning component for computing a threshold on which selection of the one or more co-occurring related named entities to return is based.

8. The system of claim 1, wherein the scoring component is further configured to compute an individual aggregate relevance score based on proximity of an occurrence of an individual co-occurring related named entity to an individual query keyword in at least one of the individual matching documents.

9. The system of claim 1, the extraction component being configured to extract all occurrences of the named entities.

10. A method comprising:

extracting named entities from documents having corresponding document identifiers;

creating and storing;

a document index that indexes the named entities by the document identifiers to indicate whether the named entities occur in the documents; and

an inverted index that indexes the document identifiers by word identifiers of words that occur in the documents, wherein the document index and the inverted index are at least partly created in advance of receiving a keyword query from a user;

receiving the keyword query from the user, the keyword query comprising keywords;

providing the keywords to the inverted index to identify individual document identifiers corresponding to individual matching documents that match one or more of the keywords of the keyword query;

retrieving direct matching document entities that directly match at least one of the keywords of the keyword query;

providing the individual document identifiers to the document index and retrieving co-occurring related named entities from the document index, wherein the co-occurring related named entities do not directly match the keywords of the keyword query but occur in the individual matching documents with the direct matching document entities;

computing aggregate relevance scores for the co-occurring related named entities that occur in the individual matching documents; and

returning one or more of the co-occurring related named entities in response to the keyword query based on the aggregate relevance scores,

wherein at least the computing the aggregate relevance scores is performed using a processing unit.

11. The method according to claim 10, wherein the named entities are stored in the document index as document metadata.

12. The method according to claim 10, wherein the named entities comprise at least one proper name of an individual.

13. The method according to claim 10, further comprising generating a query-dependent caption for at least one of the individual matching documents.

14. The method according to claim 10, further comprising:

computing a score for individual occurrences of the co-occurring related named entities based on proximity of the individual occurrences to individual keywords in the individual matching documents.

15. One or more computer-readable memory devices or storage devices having computer-readable instructions stored thereon that, when executed by one or more computing devices, cause the one or more computing devices to perform:

extracting named entities from documents having corresponding document identifiers;

creating and storing;

a document index that indexes the named entities by the document identifiers to indicate whether the named entities occur in the documents; and

an inverted index that indexes the document identifiers by word identifiers of words that occur in the documents, wherein the document index and the inverted index are at least partly created in advance of receiving a keyword query from a user;

receiving the keyword query from the user, the keyword query comprising keywords;

providing the keywords to the inverted index to identify individual document identifiers corresponding to individual matching documents that match one or more of the keywords of the keyword query;

retrieving direct matching document entities that directly match at least one of the keywords of the keyword query;

providing the individual document identifiers to the document index and retrieving co-occurring related named entities from the document index, wherein the co-occurring related named entities do not directly match the keywords of the keyword query but occur in the individual matching documents with the direct matching document entities;

computing aggregate relevance scores for the co-occurring related named entities that occur in the individual matching documents; and

returning one or more of the co-occurring related named entities in response to the keyword query based on the aggregate relevance scores.

16. The one or more computer-readable memory devices or storage devices according to claim 15, the individual matching documents comprising a top matching subset of documents for the keyword query.

17. The one or more computer-readable memory devices or storage devices according to claim 15, having further computer-readable instructions stored thereon that when executed by one or more computing devices cause the one or more computing devices to perform:

ranking the co-occurring related named entities based on a number of matching keywords.

18. The one or more computer-readable memory devices or storage devices according to claim 15, having further computer-readable instructions stored thereon that when executed by one or more computing devices cause the one or more computing devices to perform:

ranking the co-occurring related named entities based on an inverse document frequency of the keywords.

19. The one or more computer-readable memory devices or storage devices according to claim 15, having further computer-readable instructions stored thereon that when executed by one or more computing devices cause the one or more computing devices to perform:

standardizing a first one of the co-occurring named entities before returning the first co-occurring named entity.

20. The one or more computer-readable memory devices or storage devices according to claim 19, the standardizing comprising standardizing an abbreviation to a corresponding unabbreviated word.