Reducing comparisons for token-based entity resolution

• US 10,191,942 B2
• Filed: 10/14/2016
• Issued: 01/29/2019
• Est. Priority Date: 10/14/2016
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Parker, Tim, Havlicek, Jim
• Primary Examiner(s): Uddin, Md I
• Application Number:
  US15/294,481
• Publication Number:
  US 20180107730A1
• Time in Patent Office: 837 Days
• Field of Search: 707736, 707737, 707749
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24575 using context

Abstract

A token-based database management system described herein may reduce an amount of comparisons during entity resolution of records. The system includes a token creator configured to create tokens from records, a token-record mapping creator configured to create a token-record mapping of tokens to records, a token importance calculator configured to calculate token importance values for the tokens, a token pruner configured to identify a token of the current record as unimportant based on token importance values of the tokens of the current record, and to remove the unimportant token from the token-record mapping, a record selector configured to select only records sharing at least one common token with the current record, and a record comparator configured to compare the current record with each of the selected records to determine whether the current record matches any of the selected records.

Claims

1. A system for reducing an amount of comparisons during entity resolution of records, the system comprising:

an in-memory database system configured to store a plurality of records; and

token-based entity resolution circuitry configured to determine whether a current record is similar to one or more other records in the database, the token-based entity resolution circuitry including;

a token creator configured to create tokens from the plurality of records;

a token-record mapping creator configured to create a token-record mapping of tokens to records;

a token importance calculator configured to calculate token importance values for the tokens, each token importance value representing a level of amount of information contained within a respective token;

a token pruner configured to identify a token of the current record as unimportant based on token importance values of the tokens of the current record, the token pruner configured to remove the unimportant token from the token-record mapping, the identification and removal of the unimportant token comprising;

identifying a token having a highest token importance value within the current record;

marking at least one token as unimportant when a token importance value of the at least one token is less than a predetermined threshold relative to the highest token importance value in the current record; and

removing the at least one unimportant token from the token-record mapping such that records linked to the at least one unimportant token are not selected for comparison with the current record; and

a record selector configured to select only records sharing at least one common token with the current record such that the at least one common token does not include the token identified as unimportant; and

a record comparator configured to compare the current record with each of the selected records to determine whether the current record matches any of the selected records.

2. The system of claim 1, wherein the database includes a relational database.

3. The system of claim 1, wherein the token creator is configured to create one or more tokens for each record using natural language processing that splits values of a respective record into individual tokens.

4. The system of claim 1, wherein the token importance values are term frequency-inverse document frequency (tf-idf) values.

5. The system of claim 1, wherein the predetermined threshold is a defined percentage of the highest token importance value.

6. The system of claim 1, wherein the records include free-form data having an unstructured data format.

7. The system of claim 1, wherein the system is an in-memory database system having a structured query language (SQL) engine configured to execute the token-based entity resolution circuitry to select records similar to the current record.

8. A non-transitory computer-readable medium storing executable instructions that when executed cause at least one processor to:

create tokens from a plurality of records stored in a relational database comprising an in-memory database system;

create a token-record mapping of tokens to records;

calculate token importance values for the tokens, each token importance value representing a level of amount of information contained within a respective token;

identify a token of a current record as unimportant based on token importance values of the tokens of the current record;

remove the unimportant token from the token-record mapping, the identification and removal of the unimportant token comprising;

identifying a token having a highest token importance value within the current record;

marking at least one token as unimportant when a token importance value of the at least one token is less than a predetermined threshold relative to the highest token importance value in the current record; and

removing the at least one unimportant token from the token-record mapping such that records linked to the at least one unimportant token are not selected for comparison with the current record;

select only records sharing at least one common token with the current record such that the at least one common token does not include the token identified as unimportant; and

compare the current record with each of the selected records to determine whether the current record matches any of the selected records.

9. The non-transitory computer-readable medium of claim 8, wherein the tokens are created using natural language processing that splits values of a respective record into individual tokens.

10. The non-transitory computer-readable medium of claim 8, wherein the token importance values are term frequency-inverse document frequency (tf-idf) values.

11. The non-transitory computer-readable medium of claim 8, wherein the predetermined threshold is a defined percentage of the highest token importance value.

12. The non-transitory computer-readable medium of claim 8, wherein the records include free-form data having an unstructured data format.

13. A computer-implemented method for entity resolution, the method comprising:

creating tokens from a plurality of records stored in a relational database comprising an in-memory database system;

creating a token-record mapping of tokens to records;

calculating token importance values for the tokens, each token importance value representing a level of amount of information contained within a respective token;

identifying a token of a current record as unimportant based on token importance values of the tokens of the current record;

removing the unimportant token from the token-record mapping, the identification and removal of the unimportant token comprising;

identifying a token having a highest token importance value within the current record;

marking at least one token as unimportant when a token importance value of the at least one token is less than a predetermined threshold relative to the highest token importance value in the current record; and

removing the at least one unimportant token from the token-record mapping such that records linked to the at least one unimportant token are not selected for comparison with the current record;

selecting only records sharing at least one common token with the current record such that the at least one common token does not include the token identified as unimportant; and

comparing the current record with each of the selected records to determine whether the current record matches any of the selected records.

14. The method of claim 13, wherein the tokens are created using natural language processing that splits values of a respective record into individual tokens.

15. The method of claim 13, wherein the token importance values are term frequency-inverse document frequency (tf-idf) values.

16. The method of claim 13, wherein the predetermined threshold is a defined percentage of the highest token importance value.

17. The method of claim 13, wherein the relational database is included as part of an in-memory database system having a structured query language (SQL) engine.