Computing Inconsistency Measures Under Differential Privacy
Open Access
- 17 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (3) , 1-27
Abstract
Assessing data quality is crucial to knowing whether and how to use the data for different purposes. Specifically, given a collection of integrity constraints, various ways have been proposed to quantify the inconsistency of a database. Inconsistency measures are particularly important when we wish to assess the quality of private data without revealing sensitive information. We study the estimation of inconsistency measures for a database protected under Differential Privacy (DP). Such estimation is nontrivial since some measures intrinsically query sensitive information, and the computation of others involves functions on underlying sensitive data. Among five inconsistency measures that have been proposed in recent work, we identify that two are intractable in the DP setting. The major challenge for the other three is high sensitivity: adding or removing one tuple from the dataset may significantly affect the outcome. To mitigate that, we model the dataset using a conflict graph and investigate private graph statistics to estimate these measures. The proposed machinery includes adapting graph-projection techniques with parameter selection optimizations on the conflict graph and a DP variant of approximate vertex cover size. We experimentally show that we can effectively compute DP estimates of the three measures on five real-world datasets with denial constraints, where the density of the conflict graphs highly varies.Keywords
All Related Versions
Funding Information
- Ontario Graduate Scholarship
- David R. Cheriton Graduate Scholarship
- Vector Research Grant
- NSERC Discovery Grant
- Alliance Grant
- Canada CIFAR AI Chair
- Universitas Brawijaya (1702/24)
- The Scharf-Ullman Endowment
- Universitas Brawijaya
This publication has 46 references indexed in Scilit:
- Semantic inconsistency measures using 3-valued logicsInternational Journal of Approximate Reasoning, 2023
- Counting and enumerating preferred database repairsTheoretical Computer Science, 2020
- On the Compliance of Rationality Postulates for Inconsistency Measures: A More or Less Complete PictureKI - Künstliche Intelligenz, 2016
- Holistic data cleaning: Putting violations into context2013
- Data Cleaning and Query Answering with Matching Dependencies and Matching FunctionsTheory of Computing Systems, 2012
- Accurate Estimation of the Degree Distribution of Private Networks2009
- Metric Functional DependenciesInternational Conference on Data Engineering, 2009
- Mechanism Design via Differential Privacy2007
- Conditional Functional Dependencies for Data Cleaning2007
- Minimal-change integrity maintenance using tuple deletionsInformation and Computation, 2005