Database Paper Browser

Back to papers

A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification

Summary: Cost-based model for repairing constraints by value modification, enabling record-linkage–style search for low-cost fixes. NP-complete in database size; two equivalence-class–based greedy heuristics with cubic-time baselines and duplicate-record detection optimizations, yielding scalable repairs with little quality loss. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
3632
Venue
SIGMOD
Year
2005
Pagerank
0.00026517055
Overall Rank
186 | 98.71%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 73 citing papers.

Rank Citing Paper Year Venue Pagerank
117 HoloClean: Holistic Data Repairs with Probabilistic Inference 2017 VLDB 0.00032346273
489 Dependencies Revisited for Improving Data Quality 2008 PODS 0.00017666558
521 Improving Data Quality: Consistency and Accuracy 2007 VLDB 0.00017199926
544 ERACER: A Database Approach for Statistical Inference and Data Cleaning 2010 SIGMOD 0.00016837417
707 Guided Data Repair 2011 VLDB 0.00014887793
818 NADEEF: A Commodity Data Cleaning System 2013 SIGMOD 0.00013866647
896 The LLUNATIC Data-Cleaning Framework 2013 VLDB 0.00013398659
992 Towards Certain Fixes with Editing Rules and Master Data 2010 VLDB 0.00012862128
1,146 KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing 2015 SIGMOD 0.00012062353
1,259 Extending Dependencies with Conditions 2007 VLDB 0.00011530536
1,313 Sampling the Repairs of Functional Dependency Violations under Hard Constraints 2010 VLDB 0.00011294367
1,370 Northstar: An Interactive Data Science System 2018 VLDB 0.00011102352
1,375 Data Cleaning: Overview and Emerging Challenges 2016 SIGMOD 0.00011088068
1,997 RPT: Relational Pre-trained Transformer Is Almost All You Need towards Democratizing Data Preparation 2021 VLDB 9.4175365e-05
2,000 Combining Quantitative and Logical Data Cleaning 2016 VLDB 9.4149531e-05
2,093 Messing Up with BART: Error Generation for Evaluating Data-Cleaning Algorithms 2016 VLDB 9.2522415e-05
2,342 Database Repairs and Consistent Query Answering: Origins and Further Developments 2019 PODS 8.7996173e-05
2,360 BigDansing: A System for Big Data Cleansing 2015 SIGMOD 8.7662564e-05
2,379 Leveraging Aggregate Constraints For Deduplication 2007 SIGMOD 8.7389578e-05
2,650 Uni-Detect: A Unified Approach to Automated Error Detection in Tables 2019 SIGMOD 8.3702577e-05
2,790 Interaction between Record Matching and Data Repairing 2011 SIGMOD 8.183645e-05
2,858 SCODED: Statistical Constraint Oriented Data Error Detection 2020 SIGMOD 8.0943841e-05
2,943 Time Series Data Cleaning: From Anomaly Detection to Anomaly Repairing 2017 VLDB 7.9931351e-05
2,947 Towards Dependable Data Repairing with Fixing Rules 2014 SIGMOD 7.9813675e-05
3,986 GDR: A System for Guided Data Repair 2010 SIGMOD 7.0454984e-05
4,411 Horizon: Scalable Dependency-driven Data Cleaning 2021 VLDB 6.780411e-05
4,539 Temporal Rules Discovery for Web Data Cleaning 2016 VLDB 6.7101516e-05
4,673 Auto-Transform: Learning-to-Transform by Patterns 2020 VLDB 6.6330436e-05
4,793 PrivateClean: Data Cleaning and Differential Privacy 2016 SIGMOD 6.5720031e-05
4,910 Sequential Data Cleaning: A Statistical Approach 2016 SIGMOD 6.5130086e-05
5,075 Enriching Data Imputation with Extensive Similarity Neighbors 2015 VLDB 6.4411251e-05
5,162 On Repairing Structural Problems In Semi-structured Data 2013 VLDB 6.4040782e-05
5,259 Explaining Repaired Data with CFDs 2018 VLDB 6.3656293e-05
5,367 Rotom: A Meta-Learned Data Augmentation Framework for Entity Matching, Data Cleaning, Text Classification, and Beyond 2021 SIGMOD 6.3159594e-05
5,386 Exploring Change – A New Dimension of Data Analytics 2019 VLDB 6.3085148e-05
5,475 Repairing Vertex Labels under Neighborhood Constraints 2014 VLDB 6.272558e-05
5,834 Self-supervised and Interpretable Data Cleaning with Sequence Generative Adversarial Networks 2023 VLDB 6.132242e-05
5,925 Semandaq: A Data Quality System Based on Conditional Functional Dependencies 2008 VLDB 6.102267e-05
5,957 NADEEF: A Generalized Data Cleaning System 2013 VLDB 6.0886414e-05
6,064 SCREEN: Stream Data Cleaning under Speed Constraints 2015 SIGMOD 6.0519891e-05
6,072 Multivariate Time Series Cleaning under Speed Constraints 2024 SIGMOD 6.0489803e-05
6,337 Finding Label and Model Errors in Perception Data With Learned Observation Assertions 2022 SIGMOD 5.9713243e-05
6,376 Explain3D: Explaining Disagreements in Disjoint Datasets 2019 VLDB 5.9606952e-05
6,416 Benchmarking Approximate Consistent Query Answering 2021 PODS 5.9489632e-05
6,606 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 5.8853432e-05
6,625 Record Linkage with Uniqueness Constraints and Erroneous Values 2010 VLDB 5.8794134e-05
6,813 Qualitative Data Cleaning 2016 VLDB 5.8246163e-05
6,987 Akane: Perplexity-Guided Time Series Data Cleaning 2024 SIGMOD 5.7903541e-05
7,156 Time Series Data Validity 2023 SIGMOD 5.7456895e-05
7,758 Learning Over Dirty Data Without Cleaning 2020 SIGMOD 5.6092261e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
40 Consistent Query Answers in Inconsistent Databases 1999 PODS 0.00047753495
93 Potter's Wheel: An Interactive Data Cleaning System 2001 VLDB 0.00034948741
200 Declarative Data Cleaning: Language, Model, and Algorithms 2001 VLDB 0.00025806865
591 On Propagation of Deletions and Annotations Through Views 2002 PODS 0.00016070218
740 AJAX: An Extensible Data Cleaning Tool 2000 SIGMOD 0.00014526147
1,003 On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases 2003 PODS 0.00012796493
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
896 The LLUNATIC Data-Cleaning Framework 2013 VLDB 0.00013398659
9,436 Constraint-Variance Tolerant Data Repairing 2016 SIGMOD 5.3332775e-05
3,291 Modeling and Querying Possible Repairs in Duplicate Detection 2009 VLDB 7.615882e-05
10,235 Repairing Property Graphs under PG-Constraints 2026 VLDB 5.1725247e-05
3,009 Dichotomies in the Complexity of Preferred Repairs 2015 PODS 7.9190412e-05
7,863 The Computation of Optimal Subset Repairs 2020 VLDB 5.5982269e-05
521 Improving Data Quality: Consistency and Accuracy 2007 VLDB 0.00017199926
7,660 Counting and Enumerating (Preferred) Database Repairs 2017 PODS 5.629471e-05
2,790 Interaction between Record Matching and Data Repairing 2011 SIGMOD 8.183645e-05
8,716 The Cost of Representation by Subset Repairs 2025 VLDB 5.4422152e-05