The Cost of Representation by Subset Repairs

Summary: Studies the extra deletions required for FD-based subset repairs to preserve subgroup representation, exposing fairness costs beyond minimum-change repairs. Establishes NP-hardness, polynomial special cases, and practical heuristics validated experimentally. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14269
Venue: VLDB
Year: 2025
Pagerank: 5.3592132e-05
Overall Rank: 8,838 | 39.37%
DOI: 10.14778/3705829.3705860

Incoming Non-self Citations Over Time

Authors

1. Yuxi Liu (Duke University)
2. Fangzhu Shen (Duke University)
3. Kushagra Ghosh (Duke University)
4. Amir Gilad (Hebrew University)
5. Benny Kimelfeld (Technion)
6. Sudeepa Roy (Duke University)

BibTeX Citation

@article{liu_vldb25,
        title = {{The Cost of Representation by Subset Repairs}},
        author = {Liu, Yuxi and Shen, Fangzhu and Ghosh, Kushagra and Gilad, Amir and Kimelfeld, Benny and Roy, Sudeepa},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {2},
        pages = {475--487},
        doi = {10.14778/3705829.3705860},
        url = {https://doi.org/10.14778/3705829.3705860},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,317	Guardrail: Automated Integrity Constraint Synthesis From Noisy Data	2026	SIGMOD	5.093636e-05
10,523	Repairing Property Graphs under PG-Constraints	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
112	HoloClean: Holistic Data Repairs with Probabilistic Inference	2017	VLDB	0.00032801121
582	ActiveClean: Interactive Data Cleaning For Statistical Modeling	2016	VLDB	0.00016148948
725	NADEEF: A Commodity Data Cleaning System	2013	SIGMOD	0.00014617251
800	The LLUNATIC Data-Cleaning Framework	2013	VLDB	0.00013911223
863	Interventional Fairness : Causal Database Repair for Algorithmic Fairness	2019	SIGMOD	0.00013531835
955	Truth Finding on the Deep Web: Is the Problem Solved?	2013	VLDB	0.00012996675
1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS	0.00010893312
2,746	Dichotomies in the Complexity of Preferred Repairs	2015	PODS	8.1725014e-05
3,905	Automated Feature Engineering for Algorithmic Fairness	2021	VLDB	7.029145e-05
6,250	Lightweight Inspection of Data Preprocessing in Native Machine Learning Pipelines	2021	CIDR	5.9418015e-05
6,293	Query Refinement for Diversity Constraint Satisfaction	2024	VLDB	5.9247942e-05
6,544	Properties of Inconsistency Measures for Databases	2021	SIGMOD	5.8461093e-05
6,664	On Multiple Semantics for Declarative Database Repairs	2020	SIGMOD	5.8090585e-05
8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS	5.502256e-05
8,103	The Computation of Optimal Subset Repairs	2020	VLDB	5.4867244e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,241	Counting Database Repairs Entailing a Query: The Case of Functional Dependencies	2022	PODS
2	9,590	Constraint-Variance Tolerant Data Repairing	2016	SIGMOD
3	10,372	From Suspicious Errors to Valid Data: On Repairing Spatio-Temporal Data via Spatial and Temporal Dependencies	2026	SIGMOD
4	2,981	Towards Dependable Data Repairing with Fixing Rules	2014	SIGMOD
5	1,332	Sampling the Repairs of Functional Dependency Violations under Hard Constraints	2010	VLDB
6	2,782	Interaction between Record Matching and Data Repairing	2011	SIGMOD
7	8,038	Counting and Enumerating (Preferred) Database Repairs	2017	PODS
8	8,103	The Computation of Optimal Subset Repairs	2020	VLDB
9	1,399	Computing Optimal Repairs for Functional Dependencies	2018	PODS
10	185	A Cost-Based Model and Effective Heuristic for Repairing Constraints by Value Modification	2005	SIGMOD