Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.18204 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912779528568832 |
|---|---|
| author | Li, Haoda Chen, Jiahui Sun, Yu Song, Shaoxu Zhang, Haiwei Yuan, Xiaojie |
| author_facet | Li, Haoda Chen, Jiahui Sun, Yu Song, Shaoxu Zhang, Haiwei Yuan, Xiaojie |
| contents | Inconsistent values are commonly encountered in real-world applications, which can negatively impact data analysis and decision-making. While existing research primarily focuses on identifying the smallest removal set to resolve inconsistencies, recent studies have shown that multiple minimum removal sets may exist, making it difficult to make further decisions. While some approaches use the most frequent values as the guidance for the subset repair, this strategy has been criticized for its potential to inaccurately identify errors. To address these issues, we consider the dependencies between attribute values to determine a more appropriate subset repair. Our main contributions include (1) formalizing the optimal subset repair problem with attribute dependencies and analyzing its computational hardness; (2) computing the exact solution using integer linear programming; (3) developing an approximate algorithm with performance guarantees based on cliques and LP relaxation; and (4) designing a probabilistic approach with an approximation bound for efficiency. Experimental results on real-world datasets validate the effectiveness of our methods in both subset repair performance and downstream applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18204 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning Dependency Models for Subset Repair Li, Haoda Chen, Jiahui Sun, Yu Song, Shaoxu Zhang, Haiwei Yuan, Xiaojie Data Structures and Algorithms Inconsistent values are commonly encountered in real-world applications, which can negatively impact data analysis and decision-making. While existing research primarily focuses on identifying the smallest removal set to resolve inconsistencies, recent studies have shown that multiple minimum removal sets may exist, making it difficult to make further decisions. While some approaches use the most frequent values as the guidance for the subset repair, this strategy has been criticized for its potential to inaccurately identify errors. To address these issues, we consider the dependencies between attribute values to determine a more appropriate subset repair. Our main contributions include (1) formalizing the optimal subset repair problem with attribute dependencies and analyzing its computational hardness; (2) computing the exact solution using integer linear programming; (3) developing an approximate algorithm with performance guarantees based on cliques and LP relaxation; and (4) designing a probabilistic approach with an approximation bound for efficiency. Experimental results on real-world datasets validate the effectiveness of our methods in both subset repair performance and downstream applications. |
| title | Learning Dependency Models for Subset Repair |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.18204 |