DBScholar

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
3693
Venue
SIGMOD
Year
2005
Pagerank
0.00026231189
Overall Rank
185 | 98.74%
DOI
10.1145/1066157.1066175

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{bohannon_sigmod05,
        title = {{A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification}},
        author = {Bohannon, Philip and Fan, Wenfei and Flaster, Michael and Rastogi, Rajeev},
        series = {{SIGMOD} '05},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1066157.1066175},
        url = {https://dl.acm.org/doi/10.1145/1066157.1066175},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 74 citing papers.

Rank Citing Paper Year Venue Pagerank
112 HoloClean: Holistic Data Repairs with Probabilistic Inference 2017 VLDB 0.00032801121
494 Dependencies Revisited for Improving Data Quality 2008 PODS 0.00017526549
533 Improving Data Quality: Consistency and Accuracy 2007 VLDB 0.0001705859
549 ERACER: A Database Approach for Statistical Inference and Data Cleaning 2010 SIGMOD 0.00016692839
714 Guided Data Repair 2011 VLDB 0.00014662041
725 NADEEF: A Commodity Data Cleaning System 2013 SIGMOD 0.00014617251
800 The LLUNATIC Data-Cleaning Framework 2013 VLDB 0.00013911223
998 Towards Certain Fixes with Editing Rules and Master Data 2010 VLDB 0.0001275238
1,101 KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing 2015 SIGMOD 0.00012168934
1,277 Extending Dependencies with Conditions 2007 VLDB 0.00011368191
1,323 Data Cleaning: Overview and Emerging Challenges 2016 SIGMOD 0.00011152602
1,332 Sampling the Repairs of Functional Dependency Violations under Hard Constraints 2010 VLDB 0.00011129529
1,392 Northstar: An Interactive Data Science System 2018 VLDB 0.00010936065
2,019 RPT: Relational Pre-trained Transformer Is Almost All You Need towards Democratizing Data Preparation 2021 VLDB 9.2983994e-05
2,041 Combining Quantitative and Logical Data Cleaning 2016 VLDB 9.2692538e-05
2,142 Messing Up with BART: Error Generation for Evaluating Data-Cleaning Algorithms 2016 VLDB 9.0975882e-05
2,398 BigDansing: A System for Big Data Cleansing 2015 SIGMOD 8.631172e-05
2,410 Leveraging Aggregate Constraints For Deduplication 2007 SIGMOD 8.6126774e-05
2,565 Database Repairs and Consistent Query Answering: Origins and Further Developments 2019 PODS 8.4116912e-05
2,728 Uni-Detect: A Unified Approach to Automated Error Detection in Tables 2019 SIGMOD 8.1995954e-05
2,782 Interaction between Record Matching and Data Repairing 2011 SIGMOD 8.1280264e-05
2,981 Towards Dependable Data Repairing with Fixing Rules 2014 SIGMOD 7.8960114e-05
2,995 Time Series Data Cleaning: From Anomaly Detection to Anomaly Repairing 2017 VLDB 7.8750141e-05
3,004 SCODED: Statistical Constraint Oriented Data Error Detection 2020 SIGMOD 7.8608629e-05
4,059 GDR: A System for Guided Data Repair 2010 SIGMOD 6.9330647e-05
4,412 Auto-Transform: Learning-to-Transform by Patterns 2020 VLDB 6.7168614e-05
4,488 Horizon: Scalable Dependency-driven Data Cleaning 2021 VLDB 6.668457e-05
4,598 Temporal Rules Discovery for Web Data Cleaning 2016 VLDB 6.6127851e-05
4,837 PrivateClean: Data Cleaning and Differential Privacy 2016 SIGMOD 6.4845444e-05
4,966 Rotom: A Meta-Learned Data Augmentation Framework for Entity Matching, Data Cleaning, Text Classification, and Beyond 2021 SIGMOD 6.4225454e-05
4,994 Sequential Data Cleaning: A Statistical Approach 2016 SIGMOD 6.4092706e-05
5,167 Enriching Data Imputation with Extensive Similarity Neighbors 2015 VLDB 6.3370748e-05
5,312 Explaining Repaired Data with CFDs 2018 VLDB 6.2698779e-05
5,338 On Repairing Structural Problems In Semi-structured Data 2013 VLDB 6.2609275e-05
5,435 Exploring Change – A New Dimension of Data Analytics 2019 VLDB 6.2207492e-05
5,518 Self-supervised and Interpretable Data Cleaning with Sequence Generative Adversarial Networks 2023 VLDB 6.1885722e-05
5,519 Repairing Vertex Labels under Neighborhood Constraints 2014 VLDB 6.1885644e-05
5,648 Consistent Query Answers in Inconsistent Probabilistic Databases 2010 SIGMOD 6.1351417e-05
6,013 Semandaq: A Data Quality System Based on Conditional Functional Dependencies 2008 VLDB 6.0094519e-05
6,050 NADEEF: A Generalized Data Cleaning System 2013 VLDB 5.9945626e-05
6,154 Multivariate Time Series Cleaning under Speed Constraints 2024 SIGMOD 5.9567243e-05
6,186 SCREEN: Stream Data Cleaning under Speed Constraints 2015 SIGMOD 5.9487817e-05
6,392 Qualitative Data Cleaning 2016 VLDB 5.8883971e-05
6,431 Finding Label and Model Errors in Perception Data With Learned Observation Assertions 2022 SIGMOD 5.8802622e-05
6,461 Explain3D: Explaining Disagreements in Disjoint Datasets 2019 VLDB 5.8718966e-05
6,674 Benchmarking Approximate Consistent Query Answering 2021 PODS 5.8066263e-05
6,723 Record Linkage with Uniqueness Constraints and Erroneous Values 2010 VLDB 5.792469e-05
7,104 Akane: Perplexity-Guided Time Series Data Cleaning 2024 SIGMOD 5.7020425e-05
7,314 Time Series Data Validity 2023 SIGMOD 5.6471526e-05
7,880 Learning Over Dirty Data Without Cleaning 2020 SIGMOD 5.5244204e-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.

Previous Page 1 / 1 Next

Semantically Similar Papers