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: 3631
Venue: SIGMOD
Year: 2005
Pagerank: 0.00029763412
Overall Rank: 265 | 98.16%
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,605	The Computation of Optimal Subset Repairs	2020	VLDB	4.697534e-05
7,867	Learning Over Dirty Data Without Cleaning	2020	SIGMOD	4.6320452e-05
8,422	Deducing Certain Fixes to Graphs	2019	VLDB	4.5167705e-05
8,745	Sparcle: Boosting the Accuracy of Data Cleaning Systems through Spatial Awareness	2024	VLDB	4.456315e-05
8,875	CerFix: A System for Cleaning Data with Certain Fixes	2011	VLDB	4.430475e-05
9,048	On Repairing Timestamps for Regular Interval Time Series	2022	VLDB	4.4039656e-05
9,056	A Data Quality Metric (DQM): How to Estimate the Number of Undetected Errors in Data Sets	2017	VLDB	4.4039656e-05
9,278	Interactive and Deterministic Data Cleaning: A Tossed Stone Raises a Thousand Ripples	2016	SIGMOD	4.3639892e-05
9,369	Constraint-Variance Tolerant Data Repairing	2016	SIGMOD	4.3481081e-05
9,434	Rock: Cleaning Data by Embedding ML in Logic Rules	2024	SIGMOD	4.3430376e-05
9,560	MTSClean: Efficient Constraint-based Cleaning for Multi-Dimensional Time Series Data	2024	VLDB	4.3254416e-05
9,749	Efficient Differential Dependency Discovery	2024	VLDB	4.2897489e-05
10,081	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD	4.1945683e-05
10,140	Analyzing Deviations from Monotonic Trends through Database Repair	2026	SIGMOD	4.1945683e-05
10,211	SHoTClean: Bridging Soft and Hard Constraints for Multivariate Time Series Cleaning	2026	SIGMOD	4.1945683e-05
10,213	Stress-Testing Causal Claims via Cardinality Repairs	2026	SIGMOD	4.1945683e-05
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1945683e-05
10,511	The Best of Both Worlds: On Repairing Timestamps and Attribute Values for Multivariate Time Series	2025	SIGMOD	4.1945683e-05
10,855	bNDCRepair: Cleaning both Data Errors and Inaccurate Constraints on Numerical Sequential Data	2025	VLDB	4.1945683e-05
11,454	Contextual Data Cleaning with Ontology FDs	2021	SIGMOD	4.1945683e-05
11,841	BART in Action: Error Generation and Empirical Evaluations of Data-Cleaning Systems	2016	SIGMOD	4.1945683e-05
11,881	Cleaning Timestamps with Temporal Constraints	2016	VLDB	4.1945683e-05
12,012	Certain Query Answering in Partially Consistent Databases	2014	VLDB	4.1945683e-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.00067660624
112	Potter's Wheel: An Interactive Data Cleaning System	2001	VLDB	0.00047045036
199	Declarative Data Cleaning: Language, Model, and Algorithms	2001	VLDB	0.00035041015
655	On Propagation of Deletions and Annotations Through Views	2002	PODS	0.00018608845
691	AJAX: An Extensible Data Cleaning Tool	2000	SIGMOD	0.00018086135
1,102	On the Decidability and Complexity of Query Answering over Inconsistent and Incomplete Databases	2003	PODS	0.00014049364

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,197	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013390321
9,369	Constraint-Variance Tolerant Data Repairing	2016	SIGMOD	4.3481081e-05
3,360	Modeling and Querying Possible Repairs in Duplicate Detection	2009	VLDB	7.1742067e-05
10,235	Repairing Property Graphs under PG-Constraints	2026	VLDB	4.1945683e-05
3,042	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	7.669374e-05
7,605	The Computation of Optimal Subset Repairs	2020	VLDB	4.697534e-05
623	Improving Data Quality: Consistency and Accuracy	2007	VLDB	0.00018996374
7,702	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	4.6736471e-05
2,823	Interaction between Record Matching and Data Repairing	2011	SIGMOD	8.0593894e-05
8,840	The Cost of Representation by Subset Repairs	2025	VLDB	4.4388652e-05