Scalable lookup-driven entity extraction from indexed document collections

• US 9,501,475 B2
• Filed: 06/03/2014
• Issued: 11/22/2016
• Est. Priority Date: 06/24/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Agrawal, Sanjay, Chakrabarti, Kaushik, Chaudhuri, Surajit, Ganti, Venkatesh
• Primary Examiner(s): LU, KUEN S
• Application Number:
  US14/294,791
• Publication Number:
  US 20140351274A1
• Time in Patent Office: 903 Days
• Field of Search: 707/622, 707/755, 707/802
• US Class Current: 1/1
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 40/295 Named entity recognition

Abstract

A set of documents is filtered for entity extraction. A list of entity strings is received. A set of token sets that covers the entity strings in the list is determined. An inverted index generated on a first set of documents is queried using the set of token sets to determine a set of document identifiers for a subset of the documents in the first set. A second set of documents identified by the set of document identifiers is retrieved from the first set of documents. The second set of documents is filtered to include one or more documents of the second set that each includes a match with at least one entity string of the list of entity strings. Entity recognition may be performed on the filtered second set of documents.

Claims

1. A method for ad-hoc entity extraction, comprising:

filtering a first set of documents to generate a second set of documents that includes documents of the first set based at least on a set of token sets that covers entity strings in a list of entity strings, the number of tokens in the set of token sets being less than the number of words of the entity strings in the list of entity strings, the set of tokens generated based on the entity strings in the list of the entity strings; and

performing entity recognition on the second set of documents.

2. The method of claim 1, wherein said filtering comprises:

querying an inverted index generated on the first set of documents using the set of covering token sets to determine a set of document identifiers for a subset of the documents in the first set;

retrieving a subset of documents from the first set identified by the set of document identifiers; and

performing entity string matching on the retrieved subset of documents.

3. The method of claim 2, further comprising:

performing said querying and said entity string matching in a manner that balances a first cost of said querying and a second cost of said entity string matching to reduce a sum of the first and second costs.

4. The method of claim 2, wherein said querying comprises:

querying the inverted index with a plurality of batch queries, each batch query using a subset of the set of covering token sets to query the inverted index.

5. The method of claim 2, further comprising:

generating the set of covering tokens to include at least some tokens that are included in a plurality of the entity strings to reduce a total number of tokens included in the set of covering tokens.

6. The method of claim 5, where said generating comprises:

generating the set of covering tokens according to a greedy heuristic.

7. The method of claim 1, wherein said filtering comprises:

filtering the first set of documents to generate the second set of documents to include documents of the first set having at least a partial match with at least one entity string in the list of entity strings.

8. The method of claim 1, further comprising:

generating a set of signatures for the entity strings in the list.

9. A system for ad-hoc entity extraction, comprising:

one or more processors;

a document filter configured to filter a first set of documents to generate a second set of documents that includes documents of the first set based at least on a set of token sets that covers entity strings in a list of entity strings,

the number of tokens in the set of token sets being less than the number of words of the entity strings in the list of entity strings,

the set of tokens generated based on the entity strings in the list of the entity strings; and

an entity recognition module configured to perform entity recognition on the second set of documents.

10. The system of claim 9, wherein the document filter comprises:

an inverted index querier configured to query an inverted index generated on the first set of documents using the set of covering token sets to determine a set of document identifiers for a subset of the documents in the first set;

a document retriever configured to retrieve a subset of documents from the first set identified by the set of document identifiers; and

an entity string matcher configured to perform entity string matching on the retrieved subset of documents.

11. The system of claim 10, wherein the inverted index querier is configured to query the inverted index with a plurality of batch queries, each batch query using a subset of the set of covering token sets to query the inverted index.

12. The system of claim 10, further comprising:

a covering token set determiner configured to generate the set of covering tokens to include at least some tokens that are included in a plurality of the entity strings to reduce a total number of tokens included in the set of covering tokens.

13. The system of claim 12, where the covering token set determiner is configured to generate the set of covering tokens according to a greedy heuristic.

14. The system of claim 9, wherein the document filter is configured to filter the first set of documents to generate the second set of documents to include documents of the first set having at least a partial match with at least one entity string in the list of entity strings.

15. A computer program product comprising a computer-readable storage memory having computer program logic recorded thereon for enabling a processor-based system to perform ad-hoc entity extraction according to a method that comprises:

filtering a first set of documents to generate a second set of documents that includes documents of the first set based at least on a list of entity strings a set of token sets that covers entity strings in a list of entity strings,

the number of tokens in the set of token sets being less than the number of words of the entity strings in the list of entity strings,

the set of tokens generated based on the entity strings in the list of the entity strings; and

performing entity recognition on the second set of documents.

16. The computer program product of claim 15, wherein said filtering comprises:

querying an inverted index generated on the first set of documents using the set of covering token sets to determine a set of document identifiers for a subset of the documents in the first set;

retrieving a subset of documents from the first set identified by the set of document identifiers; and

performing entity string matching on the retrieved subset of documents.

17. The computer program product of claim 16, wherein said querying comprises:

querying the inverted index with a plurality of batch queries, each batch query using a subset of the set of covering token sets to query the inverted index.

18. The computer program product of claim 16, the method further comprising:

generating the set of covering tokens to include at least some tokens that are included in a plurality of the entity strings to reduce a total number of tokens included in the set of covering tokens.

19. The computer program product of claim 18, where said generating comprises:

generating the set of covering tokens according to a greedy heuristic.

20. The computer program product of claim 15, wherein said filtering comprises:

filtering the first set of documents to generate the second set of documents to include documents of the first set having at least a partial match with at least one entity string in the list of entity strings.