Scalable binning for big data deduplication
A very efficient computer system is presented to generate all pairs of records that have a certain similarity. Similarity is defined in terms of the textual similarity of the record attributes and/or absolute difference for numeric record attributes. Software assigns each record to a number of bins, and then compares pairs of records that belong to the same bin. This is more efficient than comparing all pairs of records since the number of records compared to each other is much smaller.
1. A computer implemented method for use in fast record deduplication comprising:
inputting, into software running on one or more computer processors, data records having multiple attributes;
inputting, into the software, local similarity functions of individual attributes with local similarity thresholds;
generating, by the software, Bin IDs based on the local similarity functions and the local similarity thresholds;
identifying local candidate pairs based on data records that share Bin IDs;
aggregating, by the software, the local candidate pairs to produce a set of global candidate pairs; and
filtering, by the software, the set of global candidate pairs by deciding whether a pair of data records represents a duplicate,
wherein the generating and identifying further comprise:
extracting building blocks from text within an attribute of a data record;
mapping the extracted building blocks to a global pre-defined order;
selecting subsets of the extracted building blocks as Bin IDs;
repeating the extracting, mapping, and selecting steps for every data record containing one or more text attributes; and
matching any two data records sharing a same Bin ID as a local candidate pair.
2. A computer implemented method for use in fast record deduplication comprising:
inputting, into software running on one or more computer processors, data records having multiple attributes;
inputting, into the software, local similarity functions of individual attributes with local similarity thresholds;
generating, by the software, Bin IDs based on the local similarity functions and the local similarity thresholds;
identifying local candidate pairs based on data records that share Bin IDs;
aggregating, by the software, the local candidate pairs to produce a set of global candidate pairs; and
filtering, by the software, the set of global candidate pairs by deciding whether a pair of data records represents a duplicate,
wherein the generating and identifying further comprise:
creating two sets of numeric bins, where the length of each numeric bin equals two times a threshold, the bins within each set are disjoint and interleaved with overlap equal to the threshold, and assigning a unique Bin ID to each bin in each set;
mapping a data record having a numeric value to two Bin IDs, one from each of the two sets of numeric bins, based on the first bin being 2*floor (numeric value/2*threshold) and the second bin being 2*floor (((numeric value+threshold)/2*threshold)+1);
repeating the mapping for every data record having a numeric value; and
matching any two data records sharing a same Bin ID as a local candidate pair.
3. A computer implemented method for use in fast record deduplication comprising:
inputting, into software running on one or more computer processors, data records having multiple attributes;
inputting, into the software, local similarity functions of individual attributes with local similarity thresholds;
generating, by the software, Bin IDs based on the local similarity functions and the local similarity thresholds;
identifying local candidate pairs by a Cartesian product of all data records sharing a same Bin ID;
aggregating, by the software, the local candidate pairs to produce a set of global candidate pairs;
filtering, by the software, the set of global candidate pairs by deciding whether a pair of data records represents a duplicate.
4. The method of claim 3 , wherein aggregating the local candidate pairs to produce a set of global candidate pairs further comprises:
intersecting the local candidate pairs to obtain the set of global candidate pairs; or
unioning the local candidate pairs to obtain the set of global candidate pairs; or
intersecting the union of the local candidate pairs to obtain the set of global candidate pairs.
5. A computer implemented method for use in fast record deduplication comprising:
inputting, into software running on one or more computer processors, data records having multiple attributes;
inputting, into the software, local similarity functions of individual attributes with local similarity thresholds;
generating, by the software, Bin IDs based on the local similarity functions and the local similarity thresholds;
identifying local candidate pairs based on data records that share Bin IDs;
aggregating, by the software, the local candidate pairs to produce a set of global candidate pairs by:
intersecting the local candidate pairs to obtain the set of global candidate pairs; or
unioning the local candidate pairs to obtain the set of global candidate pairs; or
intersecting the union of the local candidate pairs to obtain the set of global candidate pairs; and
filtering, by the software, the set of global candidate pairs by deciding whether a pair of data records represents a duplicate.
6. A system for performing fast record deduplication comprising at least one non-transitory computer-readable medium containing computer program instructions that when executed by at least one computer processor causes the at least one computer processor to perform the steps of:
inputting data records having multiple attributes;
inputting local similarity functions of individual attributes with local similarity thresholds;
generating Bin IDs based on the local similarity functions and the local similarity thresholds;
identifying local candidate pairs based on data records that share Bin IDs;
aggregating the local candidate pairs to produce a set of global candidate pairs; and
filtering the set of global candidate pairs by deciding whether a pair of data records represents a duplicate,
wherein the generating and identifying further comprise:
extracting building blocks from text within an attribute of a data record;
mapping the extracted building blocks to a global pre-defined order;
selecting subsets of the extracted building blocks as Bin IDs;
repeating the extracting, mapping, and selecting steps for every data record containing one or more text attributes; and
matching any two data records sharing a same Bin ID as a local candidate pair.
7. A system for performing fast record deduplication comprising at least one non-transitory computer-readable medium containing computer program instructions that when executed by at least one computer processor causes the at least one computer processor to perform the steps of:
inputting data records having multiple attributes;
inputting local similarity functions of individual attributes with local similarity thresholds;
generating Bin IDs based on the local similarity functions and the local similarity thresholds;
identifying local candidate pairs based on data records that share Bin IDs;
aggregating the local candidate pairs to produce a set of global candidate pairs; and
filtering the set of global candidate pairs by deciding whether a pair of data records represents a duplicate,
wherein the generating and identifying further comprise:
creating two sets of numeric bins, where the length of each numeric bin equals two times a threshold, the bins within each set are disjoint and interleaved with overlap equal to the threshold, and assigning a unique Bin ID to each bin in each set;
mapping a data record having a numeric value to two Bin IDs, one from each of the two sets of numeric bins, based on the first bin being 2*floor (numeric value/2*threshold) and the second bin being 2*floor (((numeric value+threshold)/2*threshold)+1);
repeating the mapping for every data record having a numeric value; and
matching any two data records sharing a same Bin ID as a local candidate pair.
8. A system for performing fast record deduplication comprising at least one non-transitory computer-readable medium containing computer program instructions that when executed by at least one computer processor causes the at least one computer processor to perform the steps of:
inputting data records having multiple attributes;
inputting local similarity functions of individual attributes with local similarity thresholds;
generating Bin IDs based on the local similarity functions and the local similarity thresholds;
identifying local candidate pairs by a Cartesian product of all data records sharing a same Bin ID;
aggregating the local candidate pairs to produce a set of global candidate pairs; and
filtering the set of global candidate pairs by deciding whether a pair of data records represents a duplicate.
9. The system of claim 8 , wherein aggregating the local candidate pairs to produce a set of global candidate pairs further comprises:
intersecting the local candidate pairs to obtain the set of global candidate pairs; or
unioning the local candidate pairs to obtain the set of global candidate pairs; or
intersecting the union of the local candidate pairs to obtain the set of global candidate pairs.
10. A system for performing fast record deduplication comprising at least one non-transitory computer-readable medium containing computer program instructions that when executed by at least one computer processor causes the at least one computer processor to perform the steps of:
inputting data records having multiple attributes;
inputting local similarity functions of individual attributes with local similarity thresholds;
generating Bin IDs based on the local similarity functions and the local similarity thresholds;
identifying local candidate pairs based on data records that share Bin IDs;
aggregating the local candidate pairs to produce a set of global candidate pairs by:
intersecting the local candidate pairs to obtain the set of global candidate pairs; or
unioning the local candidate pairs to obtain the set of global candidate pairs; or
intersecting the union of the local candidate pairs to obtain the set of global candidate pairs; and
filtering the set of global candidate pairs by deciding whether a pair of data records represents a duplicate.