Method and system for large scale data curation
Inventors
Bates-Haus, Nikolaus • Beskales, George • Bruckner, Daniel Meir • Ilyas, Ihab F. • Pagan, Alexander Richter • Stonebraker, Michael Ralph
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Abstract
An end-to-end data curation system and the various methods used in linking, matching, and cleaning large-scale data sources. The goal of this system is to provide scalable and efficient record deduplication. The system uses a crowd of experts to train the system. The system operator can optionally provide a set of hints to reduce the number of questions send to the experts. The system solves the problem of schema mapping and record deduplication a holistic way by unifying these problems into a unified linkage problem.
Core Innovation
An end-to-end data curation system performs record deduplication and schema mapping using a unified object linkage framework. The system separates roles between a system operator and a crowd of data experts, where data experts provide high level linkage criteria through a question generation and question selector subsystem that generates questions for the data experts to turn into answered questions. Raw data from one or more database storage sources is normalized and transformed into cleaned data by a data cleaning subsystem, and collected statistics about the cleaned data are provided to a model generator subsystem.
The model generator subsystem generates an initial linkage model from collected statistics and high level linkage criteria, where the high level linkage criteria includes hints from the data experts consisting of keys and anti-keys. The initial linkage model is based on initial rules represented as a Boolean formula in disjunctive normal form (DNF) to target high recall and moderate precision. The object linkage subsystem applies object linkage in computer memory on object pairs to separate linked object pairs from non-linked object pairs, using attribute similarity predicates and the DNF rules constructed such that most linked object pairs satisfy the formula while a minimal number of non-linked object pairs satisfy the formula.
The object linkage subsystem improves the initial linkage model into an enhanced linkage model by abstracting rows/records into a first set of objects and abstracting columns/fields/attributes into a second set of objects, and iteratively performing object linkage on the first set of objects and the second set of objects. Object linkage on the first set of objects performs record deduplication, while object linkage on the second set of objects performs schema mapping. The system further selects an optimal set of features from object pairs to identify possibly linked object pairs.
To reduce training data required for record deduplication, the system selects a small sample of records from one or more database storage sources and links the records into record pairs based on a linkage model. A stratified sampling process partitions selected record pairs into bins with specified similarity ranges, creates questions about the similarity of the record pairs, and selects questions from each bin proportional to the square root of the bin size multiplied by the variance of the labels in the bin. Stratified sampling is continued iteratively until the precision and recall of the enhanced linkage model are above minimum precision and recall required by a system operator, or until precision and recall do not significantly change from a previous version.
Claims Coverage
The document contains three independent claims, covering object linkage with DNF rules and expert-provided keys and anti-keys, a stratified active learning approach to reduce training data for record deduplication, and an end-to-end data curation system that performs record deduplication and schema mapping via iterative object linkage over abstracted record and attribute objects.
Dnf rule application for object pair linkage
Applying rules represented as a Boolean formula in disjunctive normal form (DNF) to object pairs to separate linked object pairs and non-linked object pairs, where the DNF is constructed with attribute similarity predicates such that most linked object pairs satisfy the formula while a minimal number of non-linked object pairs satisfy the formula.
Initial DNF rules from collected statistics and keys/anti-keys hints
Generating initial rules in disjunctive normal form (DNF) based on collected statistics from the database storage sources and based on hints from data experts, where the hints consist of keys and anti-keys and the rules guarantee high recall and moderate precision.
Stratified sampling with similarity bins to reduce record-deduplication training data
Reducing training data required for record deduplication by selecting a small sample of records, linking records into record pairs based on a linkage model, selecting a small subset of record pairs using stratified sampling that partitions selected record pairs into bins with specified similarity ranges, creates questions about similarity, selects questions from each bin proportional to the square root of the bin size multiplied by the variance of the labels in the bin, sends questions to data experts for labeling, and generates an enhanced linkage model from the labeled questions.
Iterative continuation of stratified sampling until precision/recall criteria
Continuing stratified sampling iteratively until the precision and recall of the enhanced linkage model are above the minimum precision and recall required by a system operator, or until the precision and recall of the enhanced linkage model did not significantly change from the previous version.
End-to-end data curation system with cleaning, model generation, and object linkage
Providing an end-to-end data curation system comprising an expert subsystem with data experts and a question generation and question selector subsystem to generate questions for data experts, a database source subsystem to store database sources, a data cleaning subsystem to normalize and transform raw data into cleaned data, a model generator subsystem to receive collected statistics and high level linkage criteria from data experts and generate an initial linkage model using high level linkage criteria that includes hints consisting of keys and anti-keys and initial rules represented as a Boolean formula in disjunctive normal form (DNF) guaranteeing high recall and moderate precision, and an object linkage subsystem to perform object linkage on object pairs from the cleaned data to separate linked object pairs and non-linked object pairs.
Unified record deduplication and schema mapping via iterative object abstraction linkage
Improving the initial linkage model into an enhanced linkage model by abstracting rows/records into a first set of objects and abstracting columns/fields/attributes into a second set of objects and iteratively performing object linkage on the first set of objects and the second set of objects, where object linkage on the first set performs record deduplication and object linkage on the second set performs schema mapping.
Optimal feature selection for identifying possibly linked pairs
In object linkage, selecting an optimal set of features from the object pairs to identify possibly linked object pairs.
Across the independent claims, the core inventive concept is to perform object linkage using DNF rules built from collected statistics and expert-provided keys and anti-keys to achieve high recall with moderate precision, to improve these rules via expert-labeled questions selected through stratified sampling based on similarity bins and label variance, and to implement an end-to-end data curation system where object linkage is applied to abstracted record objects for deduplication and abstracted attribute objects for schema mapping.
Stated Advantages
Initial rules guarantee high recall and moderate precision.
Enhanced linkage model precision and recall can be maintained above minimum required by a system operator.
Reduces training data required for record deduplication.
Documented Applications
Record deduplication from cleaned data using object linkage on abstracted rows/records into a first set of objects.
Schema mapping from cleaned data using object linkage on abstracted columns/fields/attributes into a second set of objects.
Reducing training data required for record deduplication by performing stratified sampling and iterative question labeling by data experts.
Interested in licensing this patent?