Selecting candidate rows for deduplication

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.

CROSS-REFERENCE TO RELATED APPLICATIONS

Not Applicable.

BACKGROUND

Background and Relevant Art

Businesses often use database systems to store data. Over time, tables of a database can become populated with records that, while not identical, are in fact duplicates (i.e., represent the same entity, such as, for example, a customer or client). Duplicate records can result from errors in data entry, data format conversions, use of different data types, etc.

Storing duplicate data is an inefficient use of computer system resources, including but not limited to storage space. Duplicate data can also cause inefficient use of financial resources. For example, when stored data is used to generate advertising mailings, two (or potentially more) sets of mailings and other communications can be sent to the same customer. These resource inefficiencies increase as the size of stored data increases.

Deduplication is a process that removes duplicate data from a data source by matching against itself and creating unique records. Deduplication can be used on database tables to at least mitigate (and approach eliminating) inefficient resource usage caused by duplicate data.

One deduplication solution includes iterating over all pairs in a table and directly computing a similarity score. This solution is relatively simple and catches virtually all duplicates but results in inferior performance time-wise (the time complexity is essentially quadratic). Another deduplication solution uses preprocessing to reduce the number of comparisons. This other solution has superior performance time-wise but compromises completeness of the results (i.e., not all duplicates are identified). One example of this other solution is a min-hash algorithm for N-gram Jaccard similarity. A further deduplication solution creates an n-gram inverse index for a list of strings (which can also be viewed as a table with a single column). The n-gram inverse index can be traversed to deduplicate the list of strings.

BRIEF SUMMARY

Embodiments of the present invention extend to methods, systems, and computer program products for selecting candidate rows for deduplication from a table. A table is accessed. The table includes a plurality of records. Each record stores at least a field value for a field and an additional field value for an additional field.

An inverse index is created for the field. For each record, the field value is decomposed into a plurality of n-grams (e.g., bigrams, trigrams, etc.). For each of the plurality of n-grams, the n-gram is mapped to a record set identifying one or more records that contain the n-gram in their field value. An additional inverse index is created for the additional field. For each record, the additional field value is decomposed into one or more features (which may or may not be n-grams). For each of the one or more features, the feature is mapped to a record set identifying one or more records that contain the feature in their additional field value.

A minimum matching score is accessed. The minimum matching score indicates 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, the inverse index and the additional inverse index are traversed together from smallest record set to largest record set among the inverse index and the additional inverse index. Traversal continues until a theoretical maximum matching score for any non-identified records does not satisfy the minimum matching score.

Traversal includes identifying a record set that includes the next smallest number of other records. Traversal also includes calculating the theoretical maximum matching score between the record and any further records not included in the identified record set based on a field weight for the field. Traversal further includes calculating an actual matching score between the record and each record included in the identified record set in accordance with the field weight and a further field weight for the further field. Any records included in an identified record set having an actual matching score that satisfies the minimum matching score are selected as duplicate candidates for the record.

In some embodiments, the field is an approximate match field and the additional field is an exact match field. In these embodiments, the inverse index for the field includes n-grams decomposed from field values. The additional inverse index includes the actual additional field values. In further embodiments, both the field and the additional field are approximate match fields. In these further embodiments, the inverse index and the additional inverse index include n-grams decomposed from field values and from additional field values respectively.

DETAILED DESCRIPTION

Embodiments of the present invention extend to methods, systems, and computer program products for selecting candidate rows for deduplication from a table. A table is accessed. The table includes a plurality of records. Each record stores at least a field value for a field and an additional field value for an additional field.

An inverse index is created for the field. For each record, the field value is decomposed into a plurality of n-grams (e.g., bigrams, trigrams, etc.). For each of the plurality of n-grams, the n-gram is mapped to a record set identifying one or more records that contain the n-gram in their field value. An additional inverse index is created for the additional field. For each record, the additional field value is decomposed into one or more features (which may or may not be n-grams). For each of the one or more features, the feature is mapped to a record set identifying one or more records that contain the feature in their additional field value.

A minimum matching score is accessed. The minimum matching score indicates 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, the inverse index and the additional inverse index are traversed together from smallest record set to largest record set among the inverse index and the additional inverse index. Traversal continues until a theoretical maximum matching score for any non-identified records does not satisfy the minimum matching score.

Traversal includes identifying a record set that includes the next smallest number of other records. Traversal also includes calculating the theoretical maximum matching score between the record and any further records not included in the identified record set based on a field weight for the field. Traversal further includes calculating an actual matching score between the record and each record included in the identified record set in accordance with the field weight and a further field weight for the further field. Any records included in an identified record set having an actual matching score that satisfies the minimum matching score are selected as duplicate candidates for the record.

In some embodiments, the field is an approximate match field and the additional field is an exact match field. In these embodiments, the inverse index for the field includes n-grams decomposed from field values. The additional inverse index includes the actual additional field values. In further embodiments, both the field and the additional field are approximate match fields. In these further embodiments, the inverse index and the additional inverse index include n-grams decomposed from field values and from additional field values respectively.

A cloud computing model can be composed of various characteristics such as, for example, on-demand self-service, broad network access, resource pooling, rapid elasticity, measured service, and so forth. A cloud computing model can also expose various service models, such as, for example, Software as a Service (“SaaS”), Platform as a Service (“PaaS”), and Infrastructure as a Service (“IaaS”). A cloud computing model can also be deployed using different deployment models such as private cloud, community cloud, public cloud, hybrid cloud, and so forth. In this description and in the claims, a “cloud computing environment” is an environment in which cloud computing is employed.

In this description and in the following claims, an “exact match” is defined as a match between two values that is a complete match. When a first value and a second value have identical features (e.g., characters or other digits) in an identical arrangement (e.g., are the same word or number), the values can be an exact match. For example, if the first value is “George” and the second value is “George”, the first value and the second value are an exact match. When a first value and a second value have any difference in features and/or arrangement of features, the values are not an exact match. For example, if the first value is “George” and the second value is “Georgia”, the first value and the second value are not an exact match.

In this description and the following claims, an “n-gram” is defined as a contiguous sequence of n items (where n represents a size) from a sequence of text or speech. An n-gram can be any combination of letters. However, the items can also be phonemes, syllables, letters, words or base pairs according to the application. n-grams can be collected from a text or speech corpus. An n-gram of size1is a “unigram”; size2is a “bigram” (or, less commonly, a “digram”); size3is a “trigram”. Larger sizes can be referred to by the value of n, e.g., “four-gram”, “five-gram”, and so on.

In this description and in the following claims, an “approximate match” is defined as a partial match (or the similarity) between two values. When a first value and second value have some identical features (e.g., characters or other digits) that are partially identically arranged (e.g., portions of different words or numbers are the same), the field values have some amount of similarity and are thus an approximate match. Values can approximately match one another in a range between 0%-100% matching. As the number of identically arranged features (the similarity) between values increases so does a corresponding approximate matching percentage.

For example, when a first value is “singer” and a second value is “singers”, the first value and the second value have some amount of similarity and are an approximate match. Likewise, when a first value is “swimming” and a second value is “running”, the first field value and second field value also have some amount of similarity and are an approximate match. However, as “singer” and “singers” have more identically arranged features (i.e., are more similar) compared to “swimming” and “running”, the percentage match between “singer” and “singers” is higher than the percentage match between “swimming” and “running”.

In some embodiments, a Dice coefficient is used calculate an approximate match percentage (indicating the similarity) between values. However, any of a variety of different mechanisms can be used to calculate an approximate match, such as, for example, Sørensen similarity index, Jaccard index, Tversky index, Levenshtein distance, etc.

Generally, a Dice coefficient between two items can be calculated according to the following equation: s=(2|X∩Y|)/(|X|+|Y|). Thus, for sets X and Y of keywords in information retrieval, the coefficient may be defined as twice the shared information (the intersection) over the sum of cardinalities. When taken as a string similarity measure, the Dice coefficient may be calculated for two strings, x and y using n-grams (e.g., bigrams, trigrams, etc.) as follows: s=2nt/nx+ny, where ntis the number of n-grams found in both strings, nxis the number of n-grams in string x, and nyis the number of n-grams in string y.

For example, one mechanism to calculate similarity between “night” and “nacht” using bigrams is to create the following bigram sets {ni,ig,gh,ht} and {na,ac,ch,ht} for each word respectively. Each set has four elements and the intersection of the two sets has one element in common, ht. Inserting these numbers into the formula, s=(2×1)/(4+4)=0.25 (25%).

Other mechanisms can use blank characters preceding and/or succeeding a word. For example, another mechanism to calculate similarity between “night” and “nacht” using bigrams is to create the following bigram sets {$n,ni,ig,gh,ht,t$} and {$n,na,ac,ch,ht,t$} for each word respectively. Each set has six elements and the intersection of the two sets has three elements in common, $n, ht, and t$. Inserting these numbers into the formula, s=(2×3)/(6+6)=0.5 (50%)

Other mechanisms to calculate similarity can use trigrams (or n-grams with higher n values). For example, one mechanism to calculate similarity between “George” and “Georgia” using trigrams is to create the following trigram sets {$$G, $Ge, Geo, eor, org, rge, ge$, and e$$} and {$$G, $Ge, Geo, eor, org, rgi, gia, ia$, a$$} for each word respectively. One set has eight elements, one set has nine elements and the intersection has five elements in common $$G, $Ge, Geo, eor, and org. Inserting these numbers into the formula s=(2×5)/(8+9)=˜0.5882 (˜58.82%).

In this description and in the following claims, an “exact match field” is defined as a field for which either an exact match or no match is indicated as the result of a comparison. When an exact match is indicated, an exact match field contributes 100% to a matching score between records. When no match is indicated, an exact match field contributes 0% to a matching score between records.

In this description and in the following claims, an “approximate match field” is defined as a field for which a similarity percentage is calculated and the calculated similarity percentage contributes to a matching score between records.

Embodiments of the invention can be used for finding candidate entries 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.

FIGS. 1A and 1Billustrate an example computer architecture100that facilitates selecting candidate records for deduplication from a table. Referring toFIGS. 1A and 1B, computer architecture100includes index creation module101and traversal module106. Index creation module101and traversal module106can be connected to one another over (or is part of) a network, such as, for example, a Local Area Network (“LAN”), a Wide Area Network (“WAN”), and even the Internet. Accordingly, index creation module101and traversal module106as well as any other connected computer systems and their components, can create message related data and exchange message related data (e.g., Internet Protocol (“IP”) datagrams and other higher layer protocols that utilize IP datagrams, such as, Transmission Control Protocol (“TCP”), Hypertext Transfer Protocol (“HTTP”), Simple Mail Transfer Protocol (“SMTP”), etc.) over the network.

Generally, index creation module101is configured to create an inverse index for each field in table. An inverse index for a field matches each feature contained in a field value for the field to a set of records that include the feature. A feature can be an n-gram (e.g., a bigram, trigram, etc.) or can be an actual (complete) field value.

As depicted, index creation module101includes decomposition module102and mapping module103. For each field, decomposition module102is configured to decompose field values into one or more features, such as, for example, n-grams. Decomposition module102can refer to field type parameters to determine what and how field values for each field of a table are to be decomposed. Field type parameters can indicate a field type, such as, for example, approximate match or exact match. When a field is indicated as an approximate match field, field type parameters can also indicate an n-gram length (e.g., n=2 [bigrams], n=3 [trigrams], etc.) to use when decomposing the field. When a field is indicated as an exact match field, decomposition module102may ignore the field.

Field type parameters can be defined by a user. Field type parameters can be contained within a table that is to be deduplicated, contained in a separate file accessible to index creation module101, or set as configuration parameters of and stored internally to index creation module101.

Mapping module103is configured to map field value features (e.g., n-grams or complete field values) to record sets within a corresponding inverse index. When accessing a feature, mapping module103can determine if the feature is already included in the appropriate inverse index. When the feature is already included, an indication of the record where the feature originated (e.g., a record ID) can be stored in a record set corresponding to the feature. When the feature is not already included, a new record set for the feature can be added to the appropriate inverse index and an indication of the record where the feature originated can be stored in the newly created record set.

Turning toFIG. 1B, for a record being checked for duplicates, traversal module106is generally configured to select duplicate candidates for the record in accordance with user defined scoring parameters. Scoring parameters can define a minimum matching score and weights for each field in a table. A minimum matching score indicates a specified level of similarity a record is to have with another record for the other record to be considered a duplicate candidate of the record. Field weights can be applied when combining scores for individual fields to calculate an actual matching score between records. Scoring parameters can be defined by a user. Scoring parameters can be contained within a table that is to be deduplicated, contained in a separate file accessible to traversal module106, or set as configuration parameters of and stored internally to traversal module106.

As depicted, traversal module106includes maximum score calculator107, actual score calculator108, and comparison module109. Traversal module106can traverse one or more inverse indices together from smallest to largest record set. For a record being checked for duplicates, initially and after each previously identified record set, traversal module106can access a record set, from among all the inverse indices, that identifies the next smallest number of other records.

Maximum score calculator107is configured to calculate a theoretical maximum matching score for any other records not identified in the accessed record set. For example, if a record includes seven trigrams for a field, and a first accessed record set identifies only the record itself, any other records in the table can at most match six of the seven trigrams for the corresponding field in this record. From this knowledge, a theoretical maximum matching score for any non-identified records can be calculated. Comparison module109is configured to compare a theoretical maximum matching score to a minimum matching score. When the theoretical maximum matching score does not satisfy the minimum matching score, traversal of the inverse indices can stop (since it is not possible for any of the non-identified records to have an actual matching score that satisfies the minimum matching score).

Actual score calculator108is configured to calculate an actual matching score for any records identified during traversal (since it is possible for identified records to have an actual matching score that satisfies the minimum matching score). Comparison module109is configured to compare actual matching scores to the minimum matching score. Any identified records having an actual matching score that satisfies the minimum matching score can be selected as duplicate candidates for the record being checked for duplicates. Duplicate candidates can be subject to further processing, including human decision making, to identify a duplicate candidate as an actual duplicate and remove the duplicate from a table.

FIG. 2illustrates a flow chart of an example method200for selecting candidate records for deduplication from a table. Method200will be described with respect to the components and data of computer architecture100.

Method200includes an act of 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 (act201). For example, referring again toFIG. 1A, index creation module101can access table111. Table111includes records112A,112B,112C, and112D and fields113and114. Records112A,112B,112C, and112D store values116,117,118, and119respectively for field113. Records112A,112B,112C, and112D store values121,121,122, and122respectively for field114. Each of records112A,112B,112C, and112D is also identified by record IDs1,2,3, and4respectively.

Index creation module101can refer to field type parameters126to determine how to treat each field of table111during inverse index creation. Field type parameters126define field113as an approximate match field. Field type parameters126also define that field values in field113are to be decomposed into n-grams of n-gram length131(e.g., 1, 2, 3, 4, etc. characters). Field type parameters126also define field114as a field of type132. Type132can represent an approximate match field or an exact match field. Thus, field type parameters132define table111as including an approximate match field and at least one other field. The at least one other field can be an approximate match field or an exact match field.

Accordingly, from field type parameters126, index creation module101can determine that field113is an approximate match field. Index creation module101can also determine that field values in field113are to be decomposed into n-grams (e.g., character sequences) of n-gram length131(e.g., 1 [unigrams], 2 [bigrams], 3 [trigrams], 4 four-grams, etc.). From field type parameters,126, index creation module101can also determine that field114is a field of type132. When type132defines an approximate match field, index creation module101can process field114as an approximate match field. On the other hand, when type132defines an exact match field, index creation module101can process field114as an exact match field.

Method200includes creating an inverse index for the field. For example, index creation module101can create inverse index133for field113.

For each record, creating an inverse index for the field includes, 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 (act203). For example, for record112A, mapping module103can map record ID1to record sets171-177(the record sets corresponding to n-gram values141-147) respectively. Similarly, for record112B, mapping module103can map record ID2to record sets171-175and177-179(the record sets corresponding to n-gram values141-145and147-149) respectively. Likewise, for record112C, mapping module103can map record ID3to record sets171-174and179(the record sets corresponding to n-gram values141-144and149) respectively. Additionally, for record112D, mapping module103can map record ID4to record sets181-184(the record sets corresponding to n-gram values151-154) respectively.

Method200includes creating an additional inverse index for the additional field. For example, index creation module101can create inverse index134for field114.

For each record, creating an inverse index for the additional field includes decomposing the additional field value into one or more features (act204). When type132defines field114as an exact match field, decomposition module102can retain field values from field114(e.g., field values121and122) without modification. That is, each of field values121and122are essentially decomposed into a single feature, which are field values121and122respectively.

On the other hand, when type132defines field114as an approximate match field, decomposition module102can decompose field values from field114into n-grams (e.g., similar to act202). When decomposing field values from field114into n-grams, n-gram length131can be used. Alternately, field type parameters126can define a different n-gram length to use when decomposing field values from field114.

For each record, creating an inverse index for the additional field includes 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 (act205). When type132defines field114as an exact match field, mapping module103can map record IDs to record sets corresponding to field values. For example, for records112A and112B, mapping module103can map record IDs1and2to record set191(the record set corresponding to value121). Similarly, for records112C and112D, mapping module103can map record IDs3and4to record set192(the record set corresponding to value122).

When type132defines field114as an approximate match field, mapping module103can map record IDs to record sets corresponding to n-grams contained in the corresponding records (e.g., similar to act203).

Method200includes an act of accessing a minimum matching score, the minimum matching 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 (act206). For example, turning toFIG. 1B, traversal module106can access scoring parameters161. Scoring parameters161define minimum matching score164. Scoring parameters161also define fields113and114to have field weights163and164respectively. When field weights are not included in scoring parameters161, each field in a table can be given equal weight.

For a record included in the table, method200includes traversing 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 theoretical maximum matching score for any non-identified records does not satisfy the minimum matching score (act207). For example, for record112A (record ID1), traversal module106can traverse inverse index133and inverse index134together from smallest record set to largest record set (among records sets171-177and191) until a theoretical maximum matching score for any non-identified records does not satisfy minimum matching score164.

Act207includes identifying a record set that includes the next smallest number of other records (act208). For example (for record ID1), since record set176includes a single record, traversal module106can initially identify record set176. Act207includes calculating the theoretical maximum matching score between the record and any further records not included in the identified record set based on a field weight for the field (act209). For example, maximum score calculator107can calculate theoretical maximum score166. Theoretical maximum score166is a theoretical maximum matching score between record112A and any of records112B,112C, and112D based on field weight162. Since record set176identifies only record112A (record ID1), theoretical maximum score166is calculated with the knowledge that records112B,112C, and112D can have at most six of seven trigrams found in field113in common with record112A and also with the knowledge of field weight162.

Act207can include comparison module109comparing theoretical max score167to minimum matching score164. In general, when a theoretical maximum score satisfies minimum matching score164, act208is repeated. For example, when theoretical max score166satisfies minimum matching score164, traversal module106can identify record set191(or some other record set from either of inverse index133or inverse index134, such as, for example, record set175or177) as including record112A and one other record.

Act209can then be repeated for the identified record set. For example, maximum score calculator107can calculate theoretical maximum score167. Theoretical maximum score167is a theoretical maximum matching score between record112A and any of records112C and112D based on field weight163. Record set176identifies record112A (record ID1) and record112B (record ID2). As such, theoretical maximum score167is calculated with the knowledge that records112C and112D do not include field value121and with the knowledge of field weight163(and with the prior knowledge that any of the other records have at most six of seven n-grams found in field113in common with record112A and with the knowledge of field weight162).

Act207can include comparison module109comparing theoretical max score167to minimum matching score164. In general, when a theoretical maximum score does not satisfy minimum matching score164, traversal is ended. For example, when theoretical max score166or theoretical max score167does not satisfy minimum matching score164, traversal module106stops traversing inverse indices133and134.

For the record, method200includes calculating an actual matching score between the record and each record included in the identified record set in accordance with the field weight and a further field weight for the further field (act210). For example, when theoretical max score167does not satisfy minimum matching score164, record112B (record ID2) is identified in record set191. Thus, for record112A, actual score calculator108can calculate actual score169for record112B. Actual score169can take into account field weights162and163.

For the record, method200includes 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 (act211). For example, for record112A, comparison module109can compare actual score169to minimum matching score164. If actual score169satisfies minimum matching score164, record112B can be included in duplicate candidates197(as a possible duplicate of record112A). On the other hand, if actual score169does not satisfy minimum matching score164, record112B is not included in duplicate candidates197. Duplicate candidates197can be subject to further processing, including human decision making, to identify a duplicate candidate as an actual duplicate of record112A and remove the duplicate from a table111.

In general, since not all records are traversed, duplicate candidates can be identified with increased time efficiency. Further, duplicate candidates can be identified with relatively high accuracy. As described, after some amount of inverse index traversal, it can be determined that a number of features (e.g., n-grams) are not shared between fields in an original record and fields in any remaining non-identified records in a table. For at least this reason, a theoretical matching score for the remaining non-identified records cannot be larger than a specified constant.

For example, for a string value with L trigrams and another string that does not have β trigrams contained in the string, the Dice coefficient between the two records cannot be larger than: 1−(1/((2L/β)−1)). For example, “hello” can be decomposed into the follow set of trigrams {$$h, $he, hel, ell, no, lo$, o$$} (L=7). If another record has a field value without two of the trigrams (β=2) in the set of trigrams, the maximum possible Dice Coefficient for the other record is: 1−(1/((2×7)/2)−1)=1−(1/(7−1))=1−⅙=˜0.8333, or ˜83.33%.

This algorithm can be used when computing a theoretical maximum matching score for a single inverse index created for an approximate match field. After decomposing a field value and fetching record sets, β can be computed for a current record's L, the maximum possible Dice coefficient can be calculated and compared to M (a minimum matching score). For a smallest record set, β=1 for any records not included in the record set along with the current record. For the next smallest record set, β=2 for any records not included in the record set along with the current record. Traversal can continue until, based on the value of β, no remaining records can satisfy M.

FIG. 3illustrates an example of traversing inverse index302for a single field301. As depicted, table300includes field301(an approximate match field). Inverse index302has been created from the values stored in field301. As indicated by traversal location306, duplicate candidates for record1are being identified. A user-defined matching value of 90% is selected (i.e., M=90%). Thus, matching values of 90% or greater for a record are considered sufficient to be a duplicate candidate.

Traversal begins at record set303, the smallest record set for a trigram contained in record1. From traversal of record set303, β=1. For β=1, the theoretical maximum matching score for other records not iterated yet is 1−(1/((2×8)/1)−1)=1−(1/(16−1))=1− 1/15=−0.9333, or 93.33%. 93.33% is greater than 90% so it is possible that other records may have actual matching scores sufficient to be considered a duplicate candidate.

Traversal then proceeds to record set304, one of the next smallest record sets for a trigram contained in record1. From traversal of record set304, β=2, for all records other than record2. For β=2, the theoretical maximum matching score for other records not iterated yet is 1−(1/((2×8)/2)−1)=1−(1/(8−1))=1− 1/7=˜0.8571, or ˜85.71%. 85.71% is less than 90% so it is not possible for any other records (other than record2) to have an actual matching score sufficient to be considered a duplicate candidate of record1. Thus, without actually visiting record3it is ruled out as a duplicate candidate for record1.

An actual matching score for record2can be calculated as: 2(7)/(8+9)=14/17=˜0.8235, or ˜82.35%. Thus, although it was theoretically possible for record2to satisfy 90%, the actual matching score for record2it is insufficient to be selected as s duplicate candidate.

Similar techniques can be applied to handle multi-field tables. Inverse indices can be created for approximate match fields (e.g., using trigrams) and exact match fields (e.g., using actual field values). A current β for each approximate match field can be saved (β indicating the number of record sets already traversed for that field). Field values are also saved for all exact match fields iterated over. A weighted sum can then be computed to determine a theoretical maximum matching score after these sets are considered. When a theoretical maximum matching score is less than M traversal stops.

FIG. 4illustrates an example of traversing inverse indices403and404for fields401and402respectively. As depicted, table400includes field401(an approximate match field) and field402(an exact match field). Inverse index403has been created from the values stored in field401. Inverse index404has been created from the values stored in field402. As indicated by traversal location408, duplicate candidates for record1are being identified. A user-defined matching value of 85% is selected (i.e., M=85%). Thus, matching values of 85% or greater for a record are considered sufficient to be a duplicate candidate. Fields401and402can be equally weighted (i.e., 50% weight for each field).

Traversal begins at record set406(size1), the smallest record set for a trigram/feature contained in record1. From traversal of record set406, β=1. For β=1, the theoretical maximum matching score for other records not iterated yet is 1−(1/((2×8)/1)−1)=1−(1/(16−1))=1− 1/15=˜0.9333, or 93.33% for field401. Since no records in inverse index404have been traversed, the theoretical maximum matching score for other records is ˜96.66% (i.e., 93.33% (0.5)+100% (0.5)) after traversing record set406. 96.66% is greater than 85% so it is possible that other records may have actual matching scores sufficient to be considered a duplicate candidate.

Traversal then proceeds to record set407(size2), the next smallest record set for a trigram/feature contained in record1. From traversal of record set407, it is determined that field402makes a contribution to an overall matching score for record2but not for any other records. The theoretical matching score for records not included in record set407and in view of β=1 for inverse index403is: 93.33% (0.5)+0% (0.5)=˜0.4666, or 46.66%. 46.66% is less than 85% so it is not possible for any other record (other than record2) to have an actual matching score sufficient to be a duplicate candidate. Thus, without actually visiting records3and4they are ruled out as duplicate candidates for record1.

An actual matching score for record2can be calculated. The contribution for field401is 2(7)/(8+9)=14/17=˜0.8235, or ˜82.35%. The contribution for field402is 100%. Thus, the actual matching score for record2is 82.35% (0.5)+100% (0.5)=˜91.17%. 91.17% is greater than 85% so record2can be considered a duplicate candidate of record1.

During traversal, it may be that multiple record sets in the same and/or in different inverse indices are of the next smallest size. Selecting a next record set in these circumstances can be arbitrary or can be according to user defined policy. In some embodiments, a policy can favor selecting record sets that yield a bigger weight reduction (weight reduction for a current iteration can be pre-computed).

FIG. 5illustrates an example of traversing inverse indices503and504for fields501and502. As depicted, table500includes field501(an approximate match field) and field502(an exact match field). Inverse index503has been created from the values stored in field501. Inverse index504has been created from the values stored in field502. As indicated by traversal location509, duplicate candidates for record1are being identified. A user-defined matching value of 85% is selected (i.e., M=85%). Thus, matching values of 85% or greater for a record are considered sufficient to be a duplicate candidate. Fields501and502can be equally weighted (i.e., 50% weight for each field).

Traversal begins at record set506(size1), the smallest record set for a trigram/feature contained in record1. From traversal of record set506, β=1. For β=1, the theoretical maximum matching score for other records not iterated yet is 1−(1/((2×8)/1)−1)=1−(1/(16−1))=1− 1/15=˜0.9333, or 93.33% for field501. Since no records in inverse index504have been traversed, the theoretical maximum matching score for other records is ˜96.66% (i.e., 93.33% (0.5)+100% (0.5)) after traversing record set506. 96.66% is greater than 80% so it is possible that other records may have actual matching scores sufficient to be considered a duplicate candidate.

After traversal of record set506, there are one or more record sets in each of inverse indices503and504that include record1and just one other record. For example, record set507includes record1and record2and record set508includes record1and record3.

If record set507is selected for traversal, β=2. For β=2, the theoretical maximum matching score for other records not iterated yet is 1−(1/((2×8)/2)−1)=1−(1/(8−1))=1− 1/7=˜0.8571, or ˜85.71%. Since no records in inverse index504have been traversed, the theoretical maximum matching score for other records is ˜92.85% (i.e., 85.71% (0.5)+100% (0.5)) after traversing record set507. 92.85% is greater than 80% so it is possible that other records may have actual matching scores sufficient to be considered a duplicate candidate.

If record set508is selected, it is determined that field502makes a contribution to an overall matching score for record3but not for any other records. The theoretical matching score for records not included in record set407and in view of β=1 for inverse index403is: 93.33% (0.5)+0% (0.5)=˜0.4666, or 46.66%. 46.66% is less than 85% so it is not possible for any other record (other than record3) to have an actual matching score sufficient to be a duplicate candidate. Thus, without actually visiting record2it is ruled out as duplicate candidate for record1.

As such, selection of record set508may be preferred over selection of record set507to yield greater weight reduction.

FIG. 6illustrates an example of traversing inverse indices603and604for fields601and602. As depicted, table600includes field601(an approximate match field) and field602(also an approximate match field). Inverse index603has been created from the values stored in field601. Inverse index604has been created from the values stored in field602. As indicated by traversal location509, duplicate candidates for record1are being identified. A user-defined matching value of 82% is selected (i.e., M=82%). Thus, matching values of 82% or greater for a record are considered sufficient to be a duplicate candidate. Field501is weighted 40% and502is weighted 60%.

As depicted, both record sets606and608are of size1so an arbitrary (or rule-based) selection can be made. InFIG. 6, record set608is arbitrarily selected for traversal.

From traversal of record set608, β=1. For β=1, the theoretical maximum matching score is 1−(1/((2×9)/1)−1)=1−(1/(18−1))=1− 1/17=˜0.9411, or 94.11% for field602. After traversal of record set608, the theoretical maximum matching score for other records not iterated yet is ˜96.46% (i.e., 100% (0.4)+94.11% (0.6)). 96.46% is greater than 82% so it is possible that other records may have actual matching scores sufficient to be considered a duplicate candidate of record1.

Traversal then continues at record set606(size1), the next smallest record set for a trigram/feature contained in record1. From traversal of record set606, β=1. For β=1, the theoretical maximum matching score is 1−(1/((2×8)/1)−1)=1−(1/(16−1))=1− 1/15=˜0.9333, or 93.33% for field601. After traversal of record set606, the theoretical maximum matching score for other records not iterated yet is ˜93.79% (i.e., 93.33% (0.4)+94.11% (0.6)). 93.79% is greater than 82% so it is possible that other records may have actual matching scores sufficient to be considered a duplicate candidate of record1.

After traversal of record set606, there are a number of remaining record sets of size2. From the record sets of size2, record set607can be arbitrarily selected for traversal. For β=2, the theoretical maximum matching score is 1−(1/((2×9)/2)−1)=1−(1/(9−1))=1−⅛=0.875, or 87.5% for field602. After traversal of record set607, the theoretical maximum matching score for other records not iterated yet is ˜89.8% (i.e., 93.33% (0.4)+87.5% (0.6)) after traversing record set608. 89.9% is greater than 82% so it is possible that other records may have actual matching scores sufficient to be considered a duplicate candidate of record1.

After traversal of record set607, there are a number of remaining record sets of size2. From the record sets of size2, record set609can be arbitrarily selected for traversal. For β=3, the theoretical maximum matching score is 1−(1/((2×9)/3)−1)=1−(1/(6−1))=1−⅕=0.8, or 80% for field602. After traversal of record set609, the theoretical maximum matching score for other records not iterated yet is ˜85.33% (i.e., 93.33% (0.4)+80% (0.6)) after traversing record set608. 85.33% is greater than 82% so it is possible that other records may have actual matching scores sufficient to be considered a duplicate candidate of record1.

After traversal of record set609, there are a number of remaining record sets of size2. From the record sets of size2, record set611can be arbitrarily selected for traversal. For β=4, the theoretical maximum matching score is 1−(1/((2×9)/4)−1)=1−(1/(4.5−1))=1− 1/3.5=˜0.7142, or 71.42% for field602. After traversal of record set611, the theoretical maximum matching score for other records not iterated yet is ˜80.18% (i.e., 93.33% (0.4)+71.42% (0.6)) after traversing record set608. 80.18% is less than 82% so it is not possible for any other record (other than record2) to have an actual matching score sufficient to be a duplicate candidate of record1.

An actual matching score for record2can be calculated. The contribution for field601is 40%×(2(7)/(8+9))=40%×( 14/17)=˜0.3294, or ˜32.94%. The contribution for field602is 60%×(2(8)/((9+10)=60%×( 16/19)=˜0.5052, or ˜50.52%. Thus, the actual matching score for record2is 32.94%+50.52%=83.46%, which is more than 82%. As such, record2is considered a duplicate of record1.

Within this description, various examples have depicted and/or described tables having one or two fields and a limited number of records. However, embodiments of the invention are equally applicable to tables having three or more fields and including tens, hundreds, thousands or even millions of records. Embodiments of the invention are also applicable to a wide variety of different arrangements of approximate match and exact match fields. For example, embodiments can be used to identify deduplication candidates within tables including three or more approximate match fields as well as tables including three or more fields overall with one or more approximate fields and one or more exact match fields.

Various different algorithms can be used to implement embodiments of the invention.FIG. 7illustrates an example algorithm700for iterating over records. Algorithm700is generally applicable for identifying deduplication candidates from tables having any configuration of approximate and exact match fields and any number of records.

Within the main loop, records are iterated over one by one and candidate records matching scores are checked. If a record's matching score is above the given threshold, these records are added to the returned set of record pairs. The algorithm uses a filtering scheme with indices so that not all records have to be considered as matching candidates.

DExactis a set of exact-match fields ordinals

DSimilaris a set of approximate-match fields ordinals

riis the i'th record in the data table.

Build_Index subroutine800initializes two data-structures value_index, trigram_index which together hold the inverse indexes for de-duplication. Value_index holds inverse indices for exact match fields and trigram_index holds inverse indices for approximate match fields. Both are functions (in code they can be represented by hash-tables) which after the subroutine's completion can apply to the following:The first, value_index is a function that maps field indexes in DExactto functions. Each function value_index[l] maps strings that appear in the l'th field for some record to a set of records that contain that specific string in the l'th field. Formally, value_index[l][v]={ri|ri,l=v}. Note that instead of the notation value_index[l][v] we've chosen the abbreviated notation value_index[l, v].The second, trigram_index is a function that maps field indexes in DSimilarto functions. Each function trigram_index[l] maps trigrams that are contained in the l′th field string value of some record to a set of records that contain that specific trigram in the l'th field. Formally, trigram_index[l][t]={ri|tεri,l}. Note that instead of the notation trigram_index[l][t] we've chosen the abbreviated notation trigram_index[l, t].

FIG. 9illustrates an example Find_Record_Duplicate_Candidates subroutine900for finding candidate records for deduplication. Find_Record_Duplicate_Candidates subroutine900represents one implementation of acts207-211of method200. Find_Record_Duplicate_Candidates subroutine900utilizes a filtering scheme to efficiently filter the records list and retrieve a (e.g., small) set of matching candidate records. Find_Record_Duplicate_Candidates subroutine900performs the following in order to return a set of record candidates:

Decompose the current record (ri)—After 2 completes, record_decomposition can hold pairs (1, S) where for each exact-match field1, record_decomposition can have one pair (1, S) where S is the set of records that share the same value with current record riin field1. And for each approximate-match field1, record_decomposition can have several pairs (1, S) for each of the trigrams in field1of record rithere can exist a pair (1, S) where S is the set of records that share the above mentioned trigram with current record riin field1.

Select a subset of record sets which still suffice in ensuring that records that were not traversed have no chance of being duplicates of current compared record. This is done by computing the theoretical maximum score possible assuming that record does not agree on currently visited field value/trigram we just considered. 7.c uses a Dice coefficient specific formula; other similarity coefficients can yield different formulas. filtered_records_sets can be a variable that holds the filtered set of records sets. Since record sets have been sorted by size, there is an increased probability of ending up with a relatively small number of records over all sets. Set S can save all traversed records while traversing records in different record sets. Set S can be used to insure that the same record is not suggested twice.