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.00029739054
Overall Rank: 268 | 98.14%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 23 of 73 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,868	Learning Over Dirty Data Without Cleaning	2020	SIGMOD	4.6276013e-05
8,014	The Computation of Optimal Subset Repairs	2020	VLDB	4.6020746e-05
8,363	Deducing Certain Fixes to Graphs	2019	VLDB	4.5311185e-05
8,741	Sparcle: Boosting the Accuracy of Data Cleaning Systems through Spatial Awareness	2024	VLDB	4.4520434e-05
8,875	CerFix: A System for Cleaning Data with Certain Fixes	2011	VLDB	4.426239e-05
9,048	On Repairing Timestamps for Regular Interval Time Series	2022	VLDB	4.3997447e-05
9,055	A Data Quality Metric (DQM): How to Estimate the Number of Undetected Errors in Data Sets	2017	VLDB	4.3997447e-05
9,283	Interactive and Deterministic Data Cleaning: A Tossed Stone Raises a Thousand Ripples	2016	SIGMOD	4.3598353e-05
9,380	Constraint-Variance Tolerant Data Repairing	2016	SIGMOD	4.3439402e-05
9,439	Rock: Cleaning Data by Embedding ML in Logic Rules	2024	SIGMOD	4.3389137e-05
9,560	MTSClean: Efficient Constraint-based Cleaning for Multi-Dimensional Time Series Data	2024	VLDB	4.3212967e-05
9,748	Efficient Differential Dependency Discovery	2024	VLDB	4.2856385e-05
10,081	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD	4.1905499e-05
10,140	Analyzing Deviations from Monotonic Trends through Database Repair	2026	SIGMOD	4.1905499e-05
10,211	SHoTClean: Bridging Soft and Hard Constraints for Multivariate Time Series Cleaning	2026	SIGMOD	4.1905499e-05
10,213	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	4.1905499e-05
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1905499e-05
10,520	The Best of Both Worlds: On Repairing Timestamps and Attribute Values for Multivariate Time Series	2025	SIGMOD	4.1905499e-05
10,859	bNDCRepair: Cleaning both Data Errors and Inaccurate Constraints on Numerical Sequential Data	2025	VLDB	4.1905499e-05
11,457	Contextual Data Cleaning with Ontology FDs	2021	SIGMOD	4.1905499e-05
11,849	BART in Action: Error Generation and Empirical Evaluations of Data-Cleaning Systems	2016	SIGMOD	4.1905499e-05
11,889	Cleaning Timestamps with Temporal Constraints	2016	VLDB	4.1905499e-05
12,020	Certain Query Answering in Partially Consistent Databases	2014	VLDB	4.1905499e-05

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
49	Consistent Query Answers in Inconsistent Databases	1999	PODS	0.00067607389
112	Potter's Wheel: An Interactive Data Cleaning System	2001	VLDB	0.00047010908
198	Declarative Data Cleaning: Language, Model, and Algorithms	2001	VLDB	0.0003505869
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018593536
690	AJAX: An Extensible Data Cleaning Tool	2000	SIGMOD	0.00018068707
1,101	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014037952

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,197	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013373177
9,380	Constraint-Variance Tolerant Data Repairing	2016	SIGMOD	4.3439402e-05
3,366	Modeling and Querying Possible Repairs in Duplicate Detection	2009	VLDB	7.1671634e-05
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1905499e-05
3,045	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.6618214e-05
8,014	The Computation of Optimal Subset Repairs	2020	VLDB	4.6020746e-05
621	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00018978331
7,701	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6690279e-05
2,830	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0515409e-05
8,839	The Cost of Representation by Subset Repairs	2025	VLDB	4.4346105e-05