Scalable binning for big data deduplication

Inventors

Beskales, George • Ilyas, Ihab F.

Assignees

Tamr Inc

Abstract

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.

Core Innovation

The document describes a scalable binning-based record deduplication approach in which data records having multiple attributes are processed by software running on one or more computer processors. For each individual attribute, local similarity functions are provided together with local similarity thresholds, and Bin IDs are generated based on the local similarity functions and the local similarity thresholds. Records that share a same Bin ID are identified as local candidate pairs, and local candidate pairs are aggregated to produce a set of global candidate pairs, which are then filtered by deciding whether a pair of data records represents a duplicate.

To generate Bin IDs from text attributes, building blocks are extracted from text within an attribute of a data record. The extracted building blocks are mapped to a global pre-defined order, subsets of the extracted building blocks are selected as Bin IDs, and the extracting, mapping, and selecting steps are repeated for every data record containing one or more text attributes. In the local candidate identification stage, any two data records sharing a same Bin ID are matched as a local candidate pair.

For numeric attributes, the document describes creating two sets of numeric bins with the length of each numeric bin equaling two times a threshold, where bins within each set are disjoint and interleaved with overlap equal to the threshold. A unique Bin ID is assigned to each bin in each set, and a data record having a numeric value is mapped to two Bin IDs, one from each of the two sets of numeric bins, based on floor-based mapping expressions. Local candidate pairs are then identified by matching any two data records sharing a same Bin ID.

Claims Coverage

The independent claims cover a computer-implemented method and corresponding system for record deduplication using per-attribute local similarity functions with local similarity thresholds to generate Bin IDs, creating local candidate pairs from shared Bin IDs, aggregating to global candidate pairs, and filtering global candidate pairs to decide duplicates. Five independent claims are provided in the claim set, with additional independent claim structures centered on specific Bin ID generation and global aggregation set-operations.

Across the independent claims, the coverage centers on generating Bin IDs from local similarity functions and local similarity thresholds, using shared Bin IDs to identify local candidate pairs, aggregating local candidate pairs into global candidate pairs, and filtering the global candidate pairs to decide duplicates. Additional refinements explicitly specify text building block extraction with a global pre-defined order, numeric two-set interleaved disjoint binning with floor-based mapping, and global candidate aggregation using intersection and/or union set operations.

Stated Advantages

Documented Applications