{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T20:36:03Z","timestamp":1780346163553,"version":"3.54.1"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"Ontario Graduate Scholarship"},{"name":"David R. Cheriton Graduate Scholarship"},{"name":"Vector Research Grant"},{"name":"NSERC Discovery grant"},{"name":"Alliance grant"},{"name":"Canada CIFAR AI Chair"},{"DOI":"10.13039\/501100006374","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1702\/24"],"award-info":[{"award-number":["1702\/24"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"The Scharf-Ullman Endowment"},{"DOI":"10.13039\/501100006374","name":"The Israeli Council for Higher Education","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,17]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3725397","type":"journal-article","created":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:23:29Z","timestamp":1750281809000},"page":"1-27","source":"Crossref","is-referenced-by-count":2,"title":["Computing Inconsistency Measures Under Differential Privacy"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8523-3019","authenticated-orcid":false,"given":"Shubhankar","family":"Mohapatra","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3764-1958","authenticated-orcid":false,"given":"Amir","family":"Gilad","sequence":"additional","affiliation":[{"name":"Hebrew University, Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4999-4937","authenticated-orcid":false,"given":"Xi","family":"He","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7156-1572","authenticated-orcid":false,"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,18]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"crossref","unstructured":"John M Abowd. 2018. The US Census Bureau adopts differential privacy. In SIGKDD. 2867--2867.","DOI":"10.1145\/3219819.3226070"},{"key":"e_1_2_2_2_1","volume-title":"Kolaitis","author":"Afrati Foto N.","year":"2009","unstructured":"Foto N. Afrati and Phokion G. Kolaitis. 2009. Repair Checking in Inconsistent Databases: Algorithms and Complexity. In ICDT. 31--41."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.24432\/C5XW20"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00461-3_26"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-012-9402-7"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157800"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Philip Bohannon Wenfei Fan Floris Geerts Xibei Jia and Anastasios Kementsietsidis. 2007. Conditional functional dependencies for data cleaning. In ICDE.","DOI":"10.1109\/ICDE.2007.367920"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.04.007"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536262"},{"key":"e_1_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Xu Chu Ihab F. Ilyas and Paolo Papotti. 2013b. Holistic data cleaning: Putting violations into context. In ICDE. 458--469.","DOI":"10.1109\/ICDE.2013.6544847"},{"key":"e_1_2_2_12_1","doi-asserted-by":"crossref","unstructured":"Wei-Yen Day Ninghui Li and Min Lyu. 2016. Publishing graph degree distribution with node differential privacy. In SIGMOD. 123--138.","DOI":"10.1145\/2882903.2926745"},{"key":"e_1_2_2_13_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Ding Bolin","year":"2017","unstructured":"Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately. Advances in Neural Information Processing Systems, Vol. 30 (2017)."},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Wei Dong Juanru Fang Ke Yi Yuchao Tao and Ashwin Machanavajjhala. 2022. R2t: Instance-optimal truncation for differentially private query evaluation with foreign keys. In SIGMOD. 759--772.","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_2_15_1","volume-title":"Differential Privacy","author":"Dwork Cynthia","unstructured":"Cynthia Dwork. 2006. Differential Privacy. In ICALP, Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener (Eds.), Vol. 4052. 1--12."},{"key":"e_1_2_2_16_1","volume-title":"Our Data","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006a. Our Data, Ourselves: Privacy Via Distributed Noise Generation. In EUROCRYPT, Serge Vaudenay (Ed.), Vol. 4004. Springer, 486--503."},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.v7i3.405"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_2_20_1","volume-title":"Kolaitis","author":"Fagin Ronald","year":"2015","unstructured":"Ronald Fagin, Benny Kimelfeld, and Phokion G. Kolaitis. 2015. Dichotomies in the Complexity of Preferred Repairs. In PODS. 3--15."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3467861.3467876"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536360.2536363"},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Amir Gilad Daniel Deutch and Sudeepa Roy. 2020. On Multiple Semantics for Declarative Database Repairs. In SIGMOD. 817--831.","DOI":"10.1145\/3318464.3389721"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39091-3_20"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2023.02.008"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873691"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_51"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_2_2_31_1","volume-title":"International Conference, PSD 2012, Palermo, Italy, September 26--28, 2012. Proceedings. Springer, 273--285","author":"Karwa Vishesh","year":"2012","unstructured":"Vishesh Karwa and Aleksandra B Slavkovi\u0107. 2012. Differentially private graphical degree sequences and synthetic graphs. In Privacy in Statistical Databases: UNESCO Chair in Data Privacy, International Conference, PSD 2012, Palermo, Italy, September 26--28, 2012. Proceedings. Springer, 273--285."},{"key":"e_1_2_2_32_1","volume-title":"International Conference, PSD 2014, Ibiza, Spain, September 17--19, 2014. Proceedings. Springer, 143--155","author":"Karwa Vishesh","year":"2014","unstructured":"Vishesh Karwa, Aleksandra B Slavkovi\u0107, and Pavel Krivitsky. 2014. Differentially private exponential random graphs. In Privacy in Statistical Databases: UNESCO Chair in Data Privacy, International Conference, PSD 2014, Ibiza, Spain, September 17--19, 2014. Proceedings. Springer, 143--155."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--642--36594--2_26"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.05.016"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342274"},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Nick Koudas Avishek Saha Divesh Srivastava and Suresh Venkatasubramanian. 2009. Metric functional dependencies. In ICDE.","DOI":"10.1109\/ICDE.2009.219"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","unstructured":"Sanjay Krishnan Jiannan Wang Michael J. Franklin Ken Goldberg and Tim Kraska. 2016. PrivateClean: Data Cleaning and Differential Privacy. In SIGMOD. ACM 937--951. https:\/\/doi.org\/10.1145\/2882903.2915248","DOI":"10.1145\/2882903.2915248"},{"key":"e_1_2_2_38_1","unstructured":"M. Lichman. 2013. UCI machine learning repository. https:\/\/archive.ics.uci.edu\/ml\/datasets\/adult."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447700"},{"key":"e_1_2_2_40_1","first-page":"1","article-title":"The Shapley Value of Tuples in Query Answering","volume":"155","author":"Livshits Ester","year":"2020","unstructured":"Ester Livshits, Leopoldo E. Bertossi, Benny Kimelfeld, and Moshe Sebag. 2020a. The Shapley Value of Tuples in Query Answering. In ICDT, Vol. 155. 20:1--20:19.","journal-title":"ICDT"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401966"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-18(2:20)2022"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360904"},{"key":"e_1_2_2_44_1","doi-asserted-by":"crossref","unstructured":"Ester Livshits Rina Kochirgan Segev Tsur Ihab F. Ilyas Benny Kimelfeld and Sudeepa Roy. 2021. Properties of Inconsistency Measures for Databases. In SIGMOD. 1182--1194.","DOI":"10.1145\/3448016.3457310"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231769"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2502.11009"},{"key":"e_1_2_2_48_1","unstructured":"Department of Transportation. 2020. Flight. Research and Innovative Technology Administration. https:\/\/data.transportation.gov\/d\/7fzd-cqts."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","unstructured":"Oleh Onyshchak. 2020. Stock Market Dataset. https:\/\/doi.org\/10.34740\/KAGGLE\/DSV\/1054465","DOI":"10.34740\/KAGGLE\/DSV\/1054465"},{"key":"e_1_2_2_50_1","volume-title":"Inconsistency measures for relational databases. arXiv preprint arXiv:1904.03403","author":"Parisi Francesco","year":"2019","unstructured":"Francesco Parisi and John Grant. 2019. Inconsistency measures for relational databases. arXiv preprint arXiv:1904.03403 (2019)."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3617838.3617844"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503595"},{"key":"e_1_2_2_53_1","unstructured":"CORGIS Dataset Project. [n. d.]. Hospitals CSV File. https:\/\/corgis-edu.github.io\/corgis\/csv\/hospitals\/."},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137631"},{"key":"e_1_2_2_55_1","unstructured":"Dan Roth. 1993. On the Hardness of Approximate Reasoning. In IJCAI. Morgan Kaufmann 613--619."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068816.2068825"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM48880.2022.9796833"},{"key":"e_1_2_2_58_1","doi-asserted-by":"crossref","unstructured":"Yuchao Tao Xi He Ashwin Machanavajjhala and Sudeepa Roy. 2020. Computing local sensitivities of counting queries with joins. In SIGMOD. 479--494.","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13218-016-0451-y"},{"key":"e_1_2_2_60_1","volume-title":"Private Data Valuation and Fair Payment in Data Marketplaces. CoRR","author":"Tian Zhihua","year":"2022","unstructured":"Zhihua Tian, Jian Liu, Jingyu Li, Xinle Cao, Ruoxi Jia, and Kui Ren. 2022. Private Data Valuation and Fair Payment in Data Marketplaces. CoRR, Vol. abs\/2210.08723 (2022)."},{"key":"e_1_2_2_61_1","volume-title":"Approximation algorithms. Georgia Inst. Tech","author":"Vazirani Vijay V","year":"1997","unstructured":"Vijay V Vazirani. 1997. Approximation algorithms. Georgia Inst. Tech (1997)."},{"key":"e_1_2_2_62_1","volume-title":"William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson.","author":"Wilson Royce J","year":"2019","unstructured":"Royce J Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. 2019. Differentially private sql with bounded user contribution. arXiv preprint arXiv:1909.01917 (2019)."},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2023.3239615"},{"key":"e_1_2_2_64_1","volume-title":"Differentially Private Generative Adversarial Network. CoRR","author":"Xie Liyang","year":"2018","unstructured":"Liyang Xie, Kaixiang Lin, Shu Wang, Fei Wang, and Jiayu Zhou. 2018. Differentially Private Generative Adversarial Network. CoRR, Vol. abs\/1802.06739 (2018). showeprint[arXiv]1802.06739 http:\/\/arxiv.org\/abs\/1802.06739"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134428"},{"key":"e_1_2_2_67_1","doi-asserted-by":"crossref","unstructured":"Jun Zhang Xiaokui Xiao and Xing Xie. 2016. PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions. In SIGMOD. 155--170.","DOI":"10.1145\/2882903.2882928"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:54:42Z","timestamp":1774983282000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725397"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,17]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6,17]]}},"alternative-id":["10.1145\/3725397"],"URL":"https:\/\/doi.org\/10.1145\/3725397","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,17]]}}}