Method for searching related entities through entity co-occurrence

• US 9,619,571 B2
• Filed: 12/02/2014
• Issued: 04/11/2017
• Est. Priority Date: 12/02/2013
• Status: Active Grant

• Current Assignee: Finch Computing LLC (Qbase, LLC)
• Original Assignee: Qbase, LLC
• Inventors: Lightner, Scott, Weckesser, Franz, Boddhu, Sanjay
• Primary Examiner(s): Shanmugasundaram, Kannan
• Application Number:
  US14/557,989
• Publication Number:
  US 20150154306A1
• Time in Patent Office: 861 Days
• Field of Search: 707741
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/901 Indexing; Data structures therefor; Storage structures for retrieval from the web G06F16/951
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

A method for searching for related entities using entity co-occurrence is disclosed. Embodiments of the method may be employed in any search system that may include at least one search engine, at least one entity co-occurrence knowledge base, an entity extraction module, and at least an entity indexed corpus. The method may extract and disambiguate entities from search queries by using an entity co-occurrence knowledge base, find extracted entities in an entity indexed corpus and finally present search results as related entities of interest.

Claims

1. A computer-implemented method comprising:

receiving, by an entity extraction computer, from a client computer a search query comprising one or more entities;

comparing, by the entity extraction computer, each respective entity with one or more co-occurrences of the respective entity in a co-occurrence in-memory database, wherein the co-occurrence database comprises one or more entries for the one or more entities, and wherein each entry for the respective entity of the one or more entities contains a semantically-related entity that identifies the respective entity, and wherein the co-occurrence is an instance of an entity of the one or more entities identified by the semantically-related entity in the corpus of documents in the co-occurrence database, and wherein the semantically-related entity corresponds to a model indicating distinct entities;

extracting, by the entity extraction computer, a subset of the one or more entities from the search query responsive to determining each respective entity of the subset exceeds a confidence score of the co-occurrence database based on a degree of certainty of co-occurrence of the entity with one or more related entities in an electronic data corpus according to the co-occurrence database;

assigning, by the entity extraction computer, an index identifier (index ID) to each of the entities in the plurality of extracted entities;

disambiguating, by the entity extraction computer, each of the entities in the plurality of extracted entities from one another based on relatedness of index IDs;

identifying, by the entity extraction computer, a subset of entities associated with each of the entities in the plurality of extracted entities based on relatedness of index IDs;

linking, by the entity extraction computer, each entity to the associated subset of entities based at least on confidence scores;

saving, by the entity extraction computer, the index ID for each of the plurality of extracted entities in the electronic data corpus, the electronic data corpus being indexed by an index ID corresponding to each of the one or more related entities;

searching, by a search server computer, the entity indexed electronic data corpus to locate the plurality of extracted entities and identify index IDs of data records in which at least two of the plurality of extracted entities co-occur; and

building, by the search server computer, a search result list having data records corresponding to the identified index IDs.

2. The method of claim 1 further comprising sorting, by the search server computer, the search result list by relevance based on the confidence score and forwarding, by the search server computer, the sorted search result list to a user device.

3. The method of claim 1 wherein the plurality of extracted entities is ranked based on the confidence score.

4. The method of claim 1 wherein the entity extraction computer associates an extracted entity with one or more co-occurring entities in the entity indexed electronic data corpus.

5. The method of claim 4 wherein the associated entities are ranked by the confidence score.

6. The method of claim 1 wherein each of the plurality of entities is selected from the group consisting of a person, an organization, a geographic location, a date, and a time.

7. A system comprising:

one or more server computers having one or more processors executing computer readable instructions for a plurality of computer modules including;

an entity co-occurrence in-memory database comprising one or more entries for each of the plurality of entities, and wherein each entry of the one or more entries for a given entity of the plurality of entities contains its semantically related entities; and

an entity extraction module configured to receive user input of search query parameters, the entity extraction module being further configured to;

extract a plurality of entities from the search query parameters by comparing each respective entity in the plurality of extracted entities with the entity co-occurrence database that includes a confidence score indicative of a degree of certainty of co-occurrence of an extracted entity with one or more related entities in an electronic data corpus, wherein the co-occurrence is an instance of the respective entity identified by the semantically-related entity in the one or more entries for the respective entity in the co-occurrence database, and wherein the semantically-related entity corresponds to a model indicating distinct entities,

assign an index identifier (index ID) to each of the entities in the plurality of extracted entities,

disambiguate each of the entities in the plurality of extracted entities from one another based on relatedness of index IDs;

identify a subset of entities associated with each of the entities in the plurality of extracted entities based on relatedness of index IDs;

link each entity to the associated subset of entities based at least on confidence scores;

save the index ID for each of the plurality of extracted entities in the electronic data corpus, the electronic data corpus being indexed by an index ID corresponding to each of the one or more related entities; and

a search server module configured to search the entity indexed electronic data corpus to locate the plurality of extracted entities and identify index IDs of data records in which at least two of the plurality of extracted entities co-occur, the search server module being further configured to build a search result list having data records corresponding to the identified index IDs.

8. The system of claim 7 wherein the search server module is further configured to sort the search result list by relevance based on the confidence score and forward the sorted search result list to a user device.

9. The system of claim 7 wherein the plurality of extracted entities is ranked based on the confidence score.

10. The system of claim 7 wherein the entity extraction module is configured to associate an extracted entity with one or more co-occurring entities in the entity indexed electronic data corpus.

11. The system of claim 10 wherein the associated entities are ranked by the confidence score.

12. The system of claim 7 wherein each of the plurality of entities is selected from the group consisting of a person, an organization, a geographic location, a date, and a time.

13. A non-transitory computer readable medium having stored thereon computer executable instructions comprising:

receiving, by an entity extraction computer, user input of search query parameters;

extracting, by the entity extraction computer, a plurality of entities from the search query parameters by comparing each entity in the plurality of extracted entities with an entity co-occurrence in-memory database that includes a confidence score indicative of a degree of certainty of co-occurrence of an extracted entity with one or more related entities in an electronic data corpus, wherein the entity co-occurrence database further comprises one or more entries for the plurality of entities, and wherein each entry of the one or more entries for a given entity of the plurality of entities contains its semantically related entities, and wherein the co-occurrence is an instance of an entity of plurality of entities identified by an entry of the one or more entries in the entity co-occurrence database, and wherein the semantically-related entity corresponds to a model indicating distinct entities,

assigning, by the entity extraction computer, an index identifier (index ID) to each of the entities in the plurality of extracted entities;

disambiguating, by the entity extraction computer, each of the entities in the plurality of extracted entities from one another based on relatedness of index IDs;

identifying, by the entity extraction computer, a subset of entities associated with each of the entities in the plurality of extracted entities based on relatedness of index IDs;

linking, by the entity extraction computer, each entity to the associated subset of entities based at least on confidence scores;

saving, by the entity extraction computer, the index ID for each of the plurality of extracted entities in the electronic data corpus, the electronic data corpus being indexed by an index ID corresponding to each of the one or more related entities;

searching, by a search server computer, the entity indexed electronic data corpus to locate the plurality of extracted entities and identify index IDs of data records in which at least two of the plurality of extracted entities co-occur; and

building, by the search server computer, a search result list having data records corresponding to the identified index IDs.

14. The computer readable medium of claim 13 wherein the instructions further comprise sorting, by the search server computer, the search result list by relevance based on the confidence score and forwarding, by the search server computer, the sorted search result list to a user device.

15. The computer readable medium of claim 13 wherein the plurality of extracted entities is ranked based on the confidence score.

16. The computer readable medium of claim 13 wherein the instructions further comprise associating, by the entity extraction computer, an extracted entity with one or more co-occurring entities in the entity indexed electronic data corpus.

17. The computer readable medium of claim 16 wherein the associated entities are ranked by the confidence score.

18. The computer readable medium of claim 13 wherein each of the plurality of entities is selected from the group consisting of a person, an organization, a geographic location, a date, and a time.