Selecting candidate rows for deduplication
AssigneeMicrosoft Corporation
InventorsYaron Zinar, Efim Hudis, Yifat Orlin, Gal Novik, Yuri Gurevich, Gad Peleg
Life of this patent
Estimating the term…
Abstract
The present invention extends to methods, systems, and computer program products for selecting candidate records for deduplication from a table. A table can be processed to compute an inverse index for each field of the table. A deduplication algorithm can traverse the inverse indices in accordance with a flexible user-defined policy to identify candidate records for deduplication. Both exact matches and approximate matches can be found.
Claims20
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, from among plurality of records, as candidates for de-duplication from a table, the method comprising:
- for a record included in the table:
- a processor collectively traversing both an inverse index and another inverse index to identify a record set from one of the inverse index and the additional inverse index to check for de-duplication candidates for the record, the record set including the record and the next smallest number of other records not yet checked as de-duplication candidates for the record, the inverse index corresponding to a field of the table and the other inverse index corresponding to another field of the table;
- calculating a maximum possible similarity between the record and any further records not included in the identified record set;
- eliminating any of the further records having a maximum possible similarity insufficient to be considered a duplicate of the record as a possible de-duplication candidate;
- calculating an actual similarity between the record and each record included in the identified record set;
- and
- selecting any records from the identified record set that have an actual similarity sufficient to be considered a duplicate of the record as a candidate for de-duplication.
The method of claim 5, wherein decomposing the field value for the other field into one or more features comprises decomposing the field value for the other field 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 field value for the other field 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 field value for the other field.
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:
- for a record included in the table:
- collectively traverse both an inverse index and another inverse index to identify a record set from one of the inverse index and the additional inverse index to check for de-duplication candidates for the record, the record set including the record and the next smallest number of other records not yet checked as de-duplication candidates for the record, the inverse index corresponding to a field of the table and the other inverse index corresponding to another field of the table;
- calculate a maximum possible similarity between the record and any further records not included in the identified record set;
- eliminate any of the further records that have a maximum possible similarity insufficient to be considered a duplicate of the record as a possible de-duplication candidate;
- calculate an actual similarity between the record and each record included in the identified record set;
- and
- select any records from the identified record set that have an actual similarity sufficient to be considered a duplicate of the record as a candidate for de-duplication.
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:
- for a record included in the table:
- a processor collectively traversing both an inverse index for a field of the table and another inverse index for another field of the table, the inverse index and the other inverse index traversed together from a smaller record set to a larger record set until a maximum possible similarity for any non-identified records is insufficient for any of the non-identified records to be considered a duplicate of the record, including:
- identifying a record set from one of the inverse index and the additional inverse index, the record set including the record and the next smallest number of other records;
- and
- calculating a maximum possible similarity between the record and any further records not included in the identified record set;
- calculating an actual similarity between the record and each record included in the identified record set;
- and
- selecting any records from the identified record set that have an actual similarity sufficient to be considered a duplicate of the record as a candidate for de-duplication.
Dependencies are inferred from the claim text.