Patent ID: 8719236

Claim:
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.