Selecting candidate rows for deduplication

1. At a computer system, the computer system including one or more processors and system memory, a method for selecting a set of one or more records as candidates for de-duplication from a table, the method comprising:

accessing a table having a plurality of records, the table including a field and an additional field, each of a plurality of records included in the table storing a field value for the field and storing an additional field value for the additional field;

creating an inverse index for the field, including for each record:

decomposing the field value into a plurality of n-grams; and

for each of the plurality of n-grams, mapping the n-gram to a record set identifying one or more records, from among the plurality of records, that contain the n-gram in their corresponding field value;

creating an additional inverse index for the additional field, including for each record:

decomposing the additional field value into one or more features; and

for each of the one or more of features, mapping the feature to a record set identifying one or more records, from among the plurality of records, that contain the feature in their additional field value;

accessing a minimum matching score, the minimum matching indicative of a level of similarity between a record and another record for the other record to be considered a duplicate candidate of the record;

for a record included in the table:

a processor collectively traversing both the inverse index and the additional inverse index together from the smallest record set to largest record set until a maximum possible matching score for any non-identified records does not satisfy the minimum matching score, including:

identifying a record set from one of the inverse index and the additional inverse index that includes the record and the next smallest number of other records; and

calculating the maximum possible matching score between the record and any further records not included in the identified record set;

calculating an actual matching score between the record and each record included in the identified record set; and

selecting duplicate candidates for the record by selecting any records included in an identified record set having an actual matching score that satisfies the minimum matching score.

2. The method as recited in claim 1 , wherein decomposing the field value into a plurality of n-grams comprises decomposing the field value into a plurality of trigrams.

3. The method as recited in claim 1 , wherein calculating the maximum possible matching score between the record and any further records not included in the identified record set comprises calculating a theoretical maximum matching score based on a number of n-grams in each of the record's field value that are not included in any of the further records' field values.

4. The method as recited in claim 1 , wherein accessing a table comprises accessing a table that includes the field, the additional field, and one or more further fields, each record also having a further field value for each of the one or more further fields.

5. The method as recited in claim 4 , wherein accessing a minimum matching score comprises accessing a minimum matching score that includes a contributing component from the field, the additional field, and each of the one or more further fields.

6. The method as recited in claim 4 , wherein at least one of the one of more further fields is an approximate match field.

7. The method as recited in claim 4 , wherein at least one of the one of more further fields is an exact match field.

8. The method as recited in claim 1 , wherein decomposing the additional field value into one or more features comprises decomposing the additional field value into a plurality of n-grams; and

wherein, for each of the one or more of features, mapping the feature to a record set identifying one or more records, from among the plurality of records, that contains the feature in their additional field value comprises, for each n-gram in the plurality of n-grams, mapping the n-gram to a record set identifying one or more records, from among the plurality of records, that contain the n-gram in their corresponding additional field value.

9. The method as recited in claim 1 , wherein decomposing the additional field value into one or more features comprises decomposing the additional field value into a single feature that is the additional field value; and

wherein, for each of the one or more of features, mapping the feature to a record set identifying one or more records, from among the plurality of records, that contain the feature in their additional field value comprises mapping the additional field value to a record set identifying one or more records, from among the plurality of records, that contain the additional field value.

10. A computer program product for use at a computer system, the computer program product for implementing a method for selecting a set of one or more records as candidates for de-duplication from a table, the computer program product comprising one or more computer storage media having stored thereon computer-executable instructions that, when executed at a processor, cause the computer system to perform the method, including the following:

access a table having a plurality of records, the table including a field and an additional field, each of a plurality of records included in the table storing a field value for the field and storing an additional field value for the additional field;

create an inverse index for the field, including for each record:

decompose the field value into a plurality of n-grams; and

for each of the plurality of n-grams, map the n-gram to a record set identifying one or more records, from among the plurality of records, that contain the n-gram in their corresponding field value;

create an additional inverse index for the additional field, including for each record:

decompose the additional field value into one or more features; and

for each of the one or more of features, map the feature to a record set identifying one or more records, from among the plurality of records, that contain the feature in their additional field value;

access a minimum matching score, the minimum matching indicative of a level of similarity between a record and another record for the other record to be considered a duplicate candidate of the record;

for a record included in the table:

collectively traverse both the inverse index and the additional inverse index together from the smallest record set to largest record set among the inverse index and the additional inverse index until a maximum possible matching score for any non-identified records does not satisfy the minimum matching score, including:

identify a record set from one of the inverse index and the additional inverse index that includes the record and the next smallest number of other records; and

calculate the maximum possible matching score between the record and any further records not included in the identified record set;

calculate an actual matching score between the record and each record included in the identified record set; and

select duplicate candidates for the record by selecting any records included in an identified record set having an actual matching score that satisfies the minimum matching score.

11. The computer program product as recited in claim 10 , wherein computer-executable instructions that, when executed, cause the computer system to decompose the field value into a plurality of n-grams comprise computer-executable instructions that, when executed, cause the computer system to decomposing the field value into a plurality of trigrams.

12. The computer program product as recited in claim 10 , wherein computer-executable instructions that, when executed, cause the computer system to calculate the maximum possible matching score between the record and any further records not included in the identified record set comprises computer-executable instructions that, when executed, cause the computer system to calculate a theoretical maximum matching score based on a number of n-grams in the record's field value that are not included in any of the further records' field values.

13. The computer program product as recited in claim 10 , wherein computer-executable instructions that, when executed, cause the computer system to access a table comprises computer-executable instructions that, when executed, cause the computer system to access a table that includes the field, the additional field, and one or more further fields, each record also having a further field value for each of the one or more further fields.

14. The computer program product as recited in claim 13 , wherein computer-executable instructions that, when executed, cause the computer system to access the minimum matching score comprise computer-executable instructions that, when executed, cause the computer system to access a minimum matching score that includes a contributing component from the field, the additional field, and each of the one or more further fields.

15. The computer program product as recited in claim 10 , wherein at least one of the one or more further fields is an approximate match field.

16. The computer program product as recited in claim 10 , wherein at least one of the one or more further fields is an exact match field.

17. A computer system for selecting candidate records for deduplication from a table, the computer system comprising:

one or more processors;

system memory; and

one or more computer storage media having stored thereon computer-executable instructions representing an index creation module and a traversal module, the index creation module configure to:

access a table having a plurality of records, the table including at least one approximate match field and one or more other fields, each of a plurality of records included in the table storing a field value for the approximate match field and storing an additional field value for each of the one or more other fields respectively;

create an inverse index for the approximate match field, including for each record:

decompose the field value into a plurality of trigrams; and

for each of the plurality of trigrams, map the trigram to a record set identifying one or more records, from among the plurality of records, that contain the trigram in their corresponding field value;

create an additional inverse index for each of the one or more other fields, including for each record:

decompose the respective additional field value into one or more features; and

for each of the one or more of features, map the feature to a record set identifying one or more records, from among the plurality of records, that contain the feature in their respective additional field value; and

wherein the traversal module is configured to:

accessing a minimum deduplication score, the minimum deduplication score indicative of a level of similarity between a record and another record for the other record to be considered a duplicate candidate of the record; and

for a record included in the table:

collectively traverse both the inverse index and each additional inverse index together from the smallest record set to largest record set among the inverse index and the additional inverse indices until a theoretical maximum deduplication score for any non-identified records does not satisfy the minimum deduplicaiton score, including:

identify a record set from one of inverse index and the additional inverse index that includes the record and the next smallest number of other records; and

calculate the theoretical maximum deduplication score between the record and any further records not included in the identified record set based on a field weight for the field and for each of the one or more additional fields;

calculate an actual deduplication score between the record and each record included in the identified record set in accordance with the field weight for the field and each of the one or more additional fields; and

select duplicate candidates for the record by selecting any records included in an identified record set having an actual deduplication score that satisfies the minimum deduplication score.

18. The computer system as recited in claim 17 , wherein at least one of the one or more other fields is an approximate match field.

19. The computer system as recited in claim 17 , wherein the traversal module being configured to collectively traverse both the inverse index and each additional inverse index together comprises the traversal module being configured to traverse to a record set for an exact match field in response to detecting that the record set and a record set for the approximate match field are both of a size that is the next smallest record set.

20. The computer system as recited in claim 17 , wherein the traversal module being configured to calculate the theoretical maximum deduplication score between the record and any further records not included in the identified record set comprises the traversal module being configured to calculate the theoretical maximum deduplication score based on a number of trigrams from the record that are not included in the further records.