Multiple candidate selection in an entity resolution system

• US 8,352,460 B2
• Filed: 03/29/2010
• Issued: 01/08/2013
• Est. Priority Date: 03/29/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Allen, Thomas B., Caceres, Barry M.
• Primary Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US12/748,596
• Publication Number:
  US 20110238654A1
• Time in Patent Office: 1,016 Days
• Field of Search: 707/708, 707/713, 707/718, 707/754, 707/758, 707/759, 707/769, 707/771, 707/780, 707/999.002, 707/999.003, 707/999.004, 707/999.005, 707/999.006
• US Class Current: 707/713
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

Techniques are disclosed for matching an inbound identity record to existing entities. Entity resolution (ER) candidate-building keys are determined for a received identity record. A query is generated from the ER candidate-building keys. When executing the query, a generic key is identified. Execution of the query is aborted upon a condition involving the generic key being satisfied.

Claims

1. A computer-implemented method to halt execution of queries containing entity resolution (ER) candidate-building keys unsuitable for generating a restricted set of candidate entities against which to match a received identity record, the method comprising:

receiving an identity record;

determining a plurality of ER candidate-building keys for the received identity record;

generating a query from one or more of the plurality of ER candidate-building keys to retrieve entities matching any of the one or more ER candidate-building keys, wherein the one or more ER candidate-building keys are derived from at least a field of the received identity record;

upon determining, during execution of the query and by operation of one or more computer processors, that at least a first ER candidate-building key of the one or more ER candidate-building keys is unsuitable for generating a restricted set of candidate entities against which to match the received identity record, aborting executing the query, wherein the restricted set of candidate entities is selected from a plurality of available entities greater in number than the restricted set of candidate entities; and

upon determining that each of the one or more ER candidate-building keys are suitable for generating the restricted set of candidate entities against which to match the received identity record, allowing the query to complete execution, to obtain the restricted set of candidate entities for the received identity record.

2. The computer-implemented method of claim 1, further comprising:

removing the unsuitable ER candidate-building key from the query to produce a modified query.

3. The computer-implemented method of claim 1, wherein the unsuitable ER candidate-building key comprises a ER candidate-building key that has retrieved a count of entities beyond a predefined threshold count.

4. The computer-implemented method of claim 1, wherein the executing of the query is aborted upon further determining that the query has retrieved a count of entities beyond a predefined threshold count, subsequent to the unsuitable ER candidate-building key being identified.

5. The computer-implemented method of claim 1, wherein the executing of the query is aborted upon further determining that the unsuitable ER candidate-building key has retrieved a count of entities beyond a predefined threshold count, subsequent to being identified as the unsuitable ER candidate-building key.

6. The computer-implemented method of claim 1, wherein the executing of the query is aborted upon further identifying another unsuitable ER candidate-building key from the one or more ER candidate-building keys.

7. The computer-implemented method of claim 1,

wherein the received identity record is matched against the restricted set of candidate entities to resolve the received identity record to a first candidate entity of the restricted set of candidate entities.

8. The computer-implemented method of claim 7, wherein the identity record includes one or more fields each containing a respective field value, wherein the plurality of ER candidate-building keys are generated based on the one or more fields included in the identity record, wherein each ER candidate-building key is a distinct variant of a field value contained in the identity record.

9. The computer-implemented method of claim 8, wherein the identity record is matched against each candidate entity in the restricted set of candidate entities and not matched against at least one available entity not in the restricted set of candidate entities, to avoid incurring processing costs associated with matching against the at least one available entity.

10. The computer-implemented method of claim 9, wherein the unsuitable ER candidate-building key is disqualified from ER candidate building, so as to facilitate removal of the unsuitable ER candidate-building key from one or more subsequent queries, prior to execution of the one or more subsequent queries, wherein one or more modified subsequent queries are generated, wherein execution of the query is aborted upon determining that the first ER candidate-building key is unsuitable comprises determining that a predefined unsuitability condition is satisfied.

11. The computer-implemented method of claim 10, wherein the predefined unsuitability condition is selected from:

(i) a first unsuitability condition comprising the first ER candidate-building key retrieving a count of candidate entities beyond a first predefined threshold count;

(ii) a second unsuitability condition comprising the first ER candidate-building key retrieving a count of candidate entities beyond a second threshold count subsequent to retrieving the first predefined threshold count of candidate entities; and

(iii) a third unsuitability condition comprising the first ER candidate-building key and a second ER candidate-building key each retrieving a respective count of candidate entities beyond a respective predefined threshold count.

12. The computer-implemented method of claim 11, wherein any candidate entities retrieved by the first ER candidate-building key are discarded upon determining that the first unsuitability condition is satisfied and that the query is not halted, wherein at least one candidate entity retrieved by a third ER candidate-building key of the one or more ER candidate-building keys is not discarded;

wherein the restricted set of candidate entities is discarded upon determining that the query is halted due to the third unsuitability condition being satisfied;

wherein the one or more ER candidate-building keys comprises two or more ER candidate building keys, and wherein the method further comprises;

removing the unsuitable ER candidate-building key from the query to produce a modified query; and

executing the modified query to retrieve a restricted set of candidate entities matching the two or more ER candidate-building keys less the unsuitable ER candidate-building key.

13. A computer-readable storage medium containing a program which, when executed, performs an operation to halt execution of queries containing entity resolution (ER) candidate-building keys unsuitable for generating a restricted set of candidate entities against which to match a received identity record, the operation comprising:

receiving an identity record;

determining a plurality of ER candidate-building keys for the received identity record;

generating a query from one or more of the plurality of ER candidate-building keys to retrieve entities matching any of the one or more ER candidate-building keys, wherein the one or more ER candidate-building keys are derived from at least a field of the received identity record;

upon determining, during execution of the query and by operation of one or more computer processors when executing the program, that at least a first ER candidate-building key of the one or more ER candidate-building keys is unsuitable for generating a restricted set of candidate entities against which to match the received identity record, aborting executing the query, wherein the restricted set of candidate entities is selected from a plurality of available entities greater in number than the restricted set of candidate entities; and

upon determining that each of the one or more ER candidate-building keys are suitable for generating the restricted set of candidate entities against which to match the received identity record, allowing the query to complete execution, to obtain the restricted set of candidate entities for the received identity record.

14. The computer-readable storage medium of claim 13, wherein the operation further comprises:

removing the unsuitable ER candidate-building key from the query to produce a modified query.

15. The computer-readable storage medium of claim 13, wherein the unsuitable ER candidate-building key comprises a ER candidate-building key that has retrieved a count of entities beyond a predefined threshold count.

16. The computer-readable storage medium of claim 13, wherein the executing of the query is aborted upon further determining that the query has retrieved a count of entities beyond a predefined threshold count, subsequent to the unsuitable ER candidate-building key being identified.

17. The computer-readable storage medium of claim 13, wherein the executing of the query is aborted upon further determining that the unsuitable ER candidate-building key has retrieved a count of entities beyond a predefined threshold count, subsequent to being identified as the unsuitable ER candidate-building key.

18. The computer-readable storage medium of claim 13, wherein the executing of the query is aborted upon further identifying another unsuitable ER candidate-building key from the one or more ER candidate-building keys.

19. A system to halt execution of queries containing entity resolution (ER) candidate-building keys unsuitable for generating a restricted set of candidate entities against which to match a received identity record, the system comprising:

one or more computer processors;

a memory containing a program which, when executed by the one or more computer processors, is configured to perform an operation comprising;

receiving an identity record;

determining a plurality of ER candidate-building keys for the received identity record;

generating a query from one or more of the plurality of ER candidate-building keys to retrieve entities matching any of the one or more ER candidate-building keys, wherein the one or more ER candidate-building keys are derived from at least a field of the received identity record;

upon determining, during execution of the query, that at least a first ER candidate-building key of the one or more ER candidate-building keys is unsuitable for generating a restricted set of candidate entities against which to match the received identity record, aborting executing the query, wherein the restricted set of candidate entities is selected from a plurality of available entities greater in number than the restricted set of candidate entities; and

upon determining that each of the one or more ER candidate-building keys are suitable for generating the restricted set of candidate entities against which to match the received identity record, allowing the query to complete execution, to obtain the restricted set of candidate entities for the received identity record.

20. The system of claim 19, wherein the operation further comprises:

removing the unsuitable ER candidate-building key from the query to produce a modified query.

21. The system of claim 19, wherein the unsuitable ER candidate-building key comprises a ER candidate-building key that has retrieved a count of entities beyond a predefined threshold count.

22. The system of claim 19, wherein the executing of the query is aborted upon further determining that the query has retrieved a count of entities beyond a predefined threshold count, subsequent to the unsuitable ER candidate-building key being identified.

23. The system of claim 19, wherein the executing of the query is aborted upon further determining that the unsuitable ER candidate-building key has retrieved a count of entities beyond a predefined threshold count, subsequent to being identified as the unsuitable ER candidate-building key.

24. The system of claim 19, wherein the executing of the query is aborted upon further identifying another unsuitable ER candidate-building key from the one or more ER candidate-building keys.