Computing Inconsistency Measures Under Differential Privacy
Summary: DP-aware estimation of database inconsistency measures via a conflict-graph model to mitigate sensitivity. Proposes graph-projection techniques and a DP approximate vertex-cover variant to estimate three measures, with experiments on five real-world denial-constraint datasets across varying conflict-graph densities.
(summarized by gpt-5-nano on Feb 09 2026)
@inproceedings{mohapatra_sigmod25,
title = {{Computing Inconsistency Measures Under Differential Privacy}},
author = {Mohapatra, Shubhankar and Gilad, Amir and He, Xi and Kimelfeld, Benny},
series = {{SIGMOD} '25},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3725397},
url = {https://dl.acm.org/doi/10.1145/3725397},
year = {2025}
}