A cost-based model and effective heuristic for repairing constraints by value modification

By Philip Bohannon, Michael Flaster, Wenfei Fan, Rajeev Rastogi. 2005

477 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Information Systems, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Information Systems

In Management Science and Operations Research

Citations in the corpus

Automated Machine Learning: State-of-The-Art and Open Challenges (2019, methodology): “[17] proposes a framework that applies different techniques from record-linkage to the search of good repairs by introducing an approach defined with two greedy algorithms with a cubic time complexity in the database size.”
HoloClean: Holistic Data Repairs with Probabilistic Inference (2017, background): “Without external domain knowledge, data re-pairing algorithms usually allow a cell to obtain any value from the active domain of their corresponding attribute, namely, the values that have appeared in the corresponding attribute of that cell [7, 12].”
KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing (2015, methodology): “For comparison with automatic data cleaning approaches, we used an equivalence-class [2] (i.”
NADEEF: a commodity data cleaning system (2013, methodology): “s [13], FDs and inds [5], and denial constraints [1].”
Data Cleaning: Overview and Emerging Challenges (2016, background): “A large body of work uses integrity constraints (ICs), a fractional of first order logic, to capture data quality rules that the database should conform to, including functional dependencies (FDs) [13], and denial constraints (DCs) [22].”
Conditional Functional Dependencies for Data Cleaning (2007, methodology): “For example, it is known [ 3 ] that if a pair t1 ,t 2 of tuples violate an FD X → A, one can resolve the inconsistency by modifying t1[A] or t2[A] such that t1[A ]= t2[A] .T hat is,FD violations can always be resolvedby modifyingvalues of some t1 (or t2) attributes in the RHSof FDs, withoutchangingt”
Interactive and Deterministic Data Cleaning (2016, methodology): “Rule-based approaches for data cleaning are divided between methods to discover the rules from clean data [11, 12, 17, 25, 40], and algorithms and systems to apply the rules over dirty data to automatically fix the detected errors [7,13,15,18,19,21,23,24,30,32,43,46].”
Guided data repair (2011, methodology): “Most of the existing data repair approaches (e.g., [2, 6, 7, 16]) focus on providing fully automated solutions using diﬀerent heuristics to select updates that would introduce minimal changes to the data, which could be risky especially for critical data.”
PrivateClean: Data Cleaning and Differential Privacy (2016, methodology): “We solve for the constraints and implications using a standard repair algorithm [6].”
Trends in Cleaning Relational Data: Consistency and Deduplication (2015, methodology): “Algorithm 4 gives the details of a data repairing algorithm with respect to a given set of FDs [17] as an example.”
Improving Data Quality: Consistency and Accuracy (2007, methodology): “Indeed, while it sufﬁces to resolve FD violations by only editing values of attributes in the RHS of FD s [5], this strategy may not terminate on CFD s , as shown by the next example.”
Data Lifecycle Challenges in Production Machine Learning (2018, background): “In the literature, cost-based models [16, 42] and conflict hypergraphs [23] are proposed.”
Combining Quantitative and Logical Data Cleaning (2015, methodology): “We show that the problem of computing statistical distortion minimal repairs is NP-hard.”
Conditional functional dependencies for capturing data inconsistencies (2008, unknown): “While a constraint repair facility will logically become part of the cleaning process supported by these systems, we are not aware of analogous functionality currently in any of the systems mentioned.”
Large-Scale Deduplication with Constraints Using Dedupalog (2009, background): “A related line of work considers the problem of automatically repairing a database instance so as to satisfy all hard constraints [52], [53].”