{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:56:06Z","timestamp":1775638566140,"version":"3.50.1"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>\n            Differential privacy has been widely adopted to release continuous- and scalar-valued information on a database without compromising the privacy of individual data records in it. The problem of querying binary- and matrix-valued information on a database in a differentially private manner has rarely been studied. However, binary- and matrix-valued data are ubiquitous in real-world applications, whose privacy concerns may arise under a variety of circumstances. In this paper, we devise an exclusive or (XOR) mechanism that perturbs binary- and matrix-valued query result by conducting an XOR operation on the query result with calibrated noises attributed to a matrix-valued Bernoulli distribution. We first rigorously analyze the privacy and utility guarantee of the proposed XOR mechanism. Then, to generate the parameters in the matrix-valued Bernoulli distribution, we develop a heuristic approach to minimize the expected square query error rate under\n            <jats:italic>\u03f5<\/jats:italic>\n            -differential privacy constraint. Additionally, to address the intractability of calculating the probability density function (PDF) of this distribution and efficiently generate samples from it, we adapt an Exact Hamiltonian Monte Carlo based sampling scheme. Finally, we experimentally demonstrate the efficacy of the XOR mechanism by considering binary data classification and social network analysis, all in a differentially private manner. Experiment results show that the XOR mechanism notably outperforms other state-of-the-art differentially private methods in terms of utility (such as classification accuracy and\n            <jats:italic>F<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            score), and even achieves comparable utility to the non-private mechanisms.\n          <\/jats:p>","DOI":"10.14778\/3446095.3446106","type":"journal-article","created":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T16:36:58Z","timestamp":1616517418000},"page":"849-862","source":"Crossref","is-referenced-by-count":9,"title":["Differentially private binary- and matrix-valued data query"],"prefix":"10.14778","volume":"14","author":[{"given":"Tianxi","family":"Ji","sequence":"first","affiliation":[{"name":"Case Western Reserve University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pan","family":"Li","sequence":"additional","affiliation":[{"name":"Case Western Reserve University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emre","family":"Yilmaz","sequence":"additional","affiliation":[{"name":"University of Houston-Downtown"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erman","family":"Ayday","sequence":"additional","affiliation":[{"name":"Case Western Reserve University and Bilkent University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanfang (Fanny)","family":"Ye","sequence":"additional","affiliation":[{"name":"Case Western Reserve University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jinyuan","family":"Sun","sequence":"additional","affiliation":[{"name":"The University of Tennessee"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3327757.3327856"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2016.74"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335326"},{"key":"e_1_2_1_4_1","unstructured":"Raman Arora and Jalaj Upadhyay. 2019. On differentially private graph sparsification and applications. In Advances in Neural Information Processing Systems. 13399--13410.  Raman Arora and Jalaj Upadhyay. 2019. On differentially private graph sparsification and applications. In Advances in Neural Information Processing Systems. 13399--13410."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CISS.2008.4558487"},{"key":"e_1_2_1_7_1","volume-title":"Statistical inference","author":"Casella George","unstructured":"George Casella and Roger L Berger . 2002. Statistical inference . Vol. 2 . Duxbury Pacific Grove , CA. George Casella and Roger L Berger. 2002. Statistical inference. Vol. 2. Duxbury Pacific Grove, CA."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243750"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2981780.2981817"},{"key":"e_1_2_1_10_1","volume-title":"The analysis of multivariate binary data. Applied statistics 21, 2","author":"Cox David R","year":"1972","unstructured":"David R Cox . 1972. The analysis of multivariate binary data. Applied statistics 21, 2 ( 1972 ), 113--120. David R Cox. 1972. The analysis of multivariate binary data. Applied statistics 21, 2 (1972), 113--120."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.036131"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2926745"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_16_1","volume-title":"GDAGAN: An Anonymization Method for Graph Data Publishing Using Generative Adversarial Network. In 2019 6th International Conference on Information Science and Control Engineering (ICISCE)","author":"Fang Junbin","year":"2019","unstructured":"Junbin Fang , Aiping Li , and Qianyue Jiang . 2019 . GDAGAN: An Anonymization Method for Graph Data Publishing Using Generative Adversarial Network. In 2019 6th International Conference on Information Science and Control Engineering (ICISCE) . IEEE , 309--313. Junbin Fang, Aiping Li, and Qianyue Jiang. 2019. GDAGAN: An Anonymization Method for Graph Data Publishing Using Generative Adversarial Network. In 2019 6th International Conference on Information Science and Control Engineering (ICISCE). IEEE, 309--313."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sigpro.2014.03.026"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5_28"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1987260.1987294"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999325.2999396"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.11"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588581"},{"key":"e_1_2_1_24_1","volume-title":"Connectivity matters: Construction and exact random sampling of connected graphs. arXiv preprint arXiv:2009.03747 1, 1","author":"Horv\u00e1t Szabolcs","year":"2020","unstructured":"Szabolcs Horv\u00e1t and Carl D Modes . 2020. Connectivity matters: Construction and exact random sampling of connected graphs. arXiv preprint arXiv:2009.03747 1, 1 ( 2020 ), 26. Szabolcs Horv\u00e1t and Carl D Modes. 2020. Connectivity matters: Construction and exact random sampling of connected graphs. arXiv preprint arXiv:2009.03747 1, 1 (2020), 26."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSM.2020.2982555"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-47436-2_15"},{"key":"e_1_2_1_27_1","volume-title":"Locally Differentially Private Analysis of Graph Statistics. arXiv preprint arXiv:2010.08688","author":"Imola Jacob","year":"2020","unstructured":"Jacob Imola , Takao Murakami , and Kamalika Chaudhuri . 2020. Locally Differentially Private Analysis of Graph Statistics. arXiv preprint arXiv:2010.08688 ( 2020 ), 26. Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2020. Locally Differentially Private Analysis of Graph Statistics. arXiv preprint arXiv:2010.08688 (2020), 26."},{"key":"e_1_2_1_28_1","volume-title":"Differentially Private Community Detection in Attributed Social Networks. In Asian Conference on Machine Learning. 16--31","author":"Ji Tianxi","year":"2019","unstructured":"Tianxi Ji , Changqing Luo , Yifan Guo , Jinlong Ji , Weixian Liao , and Pan Li . 2019 . Differentially Private Community Detection in Attributed Social Networks. In Asian Conference on Machine Learning. 16--31 . Tianxi Ji, Changqing Luo, Yifan Guo, Jinlong Ji, Weixian Liao, and Pan Li. 2019. Differentially Private Community Detection in Attributed Social Networks. In Asian Conference on Machine Learning. 16--31."},{"key":"e_1_2_1_29_1","volume-title":"Community detection in online social networks: a differentially private and parsimonious approach","author":"Ji Tianxi","year":"2020","unstructured":"Tianxi Ji , Changqing Luo , Yifan Guo , Qianlong Wang , Lixing Yu , and Pan Li. 2020. Community detection in online social networks: a differentially private and parsimonious approach . IEEE transactions on computational social systems 7, I ( 2020 ), 151--163. Tianxi Ji, Changqing Luo, Yifan Guo, Qianlong Wang, Lixing Yu, and Pan Li. 2020. Community detection in online social networks: a differentially private and parsimonious approach. IEEE transactions on computational social systems 7, I (2020), 151--163."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2514689"},{"key":"e_1_2_1_32_1","volume-title":"Information theory and statistics","author":"Kullback Solomon","unstructured":"Solomon Kullback . 1997. Information theory and statistics . Courier Corporation . Solomon Kullback. 1997. Information theory and statistics. Courier Corporation."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.402252"},{"key":"e_1_2_1_34_1","volume-title":"Simulating hamiltonian dynamics","author":"Leimkuhler Benedict","unstructured":"Benedict Leimkuhler and Sebastian Reich . 2004. Simulating hamiltonian dynamics . Vol. 14 . Cambridge university press . Benedict Leimkuhler and Sebastian Reich. 2004. Simulating hamiltonian dynamics. Vol. 14. Cambridge university press."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999134.2999195"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516686"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2019.2895970"},{"key":"e_1_2_1_39_1","first-page":"21","article-title":"Dependence Makes You Vulnberable: Differential Privacy Under Dependent Tuples","volume":"16","author":"Liu Changchang","year":"2016","unstructured":"Changchang Liu , Supriyo Chakraborty , and Prateek Mittal . 2016 . Dependence Makes You Vulnberable: Differential Privacy Under Dependent Tuples .. In NDSS , Vol. 16. 21 -- 24 . Changchang Liu, Supriyo Chakraborty, and Prateek Mittal. 2016. Dependence Makes You Vulnberable: Differential Privacy Under Dependent Tuples.. In NDSS, Vol. 16. 21--24.","journal-title":"NDSS"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2845388"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmva.2005.06.008"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159913.1159930"},{"key":"e_1_2_1_43_1","unstructured":"Kimberly McCullough. 2016. Why Government Use of Social Media Monitoring Software Is a Direct Threat to Our Liberty and Privacy. https:\/\/www.aclu.org\/blog\/privacy-technology\/surveillance-technologies\/why-government-use-social-media-monitoring  Kimberly McCullough. 2016. Why Government Use of Social Media Monitoring Software Is a Direct Threat to Our Liberty and Privacy. https:\/\/www.aclu.org\/blog\/privacy-technology\/surveillance-technologies\/why-government-use-social-media-monitoring"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1397735.1397742"},{"key":"e_1_2_1_45_1","volume-title":"Jos\u00e9 S Andrade Jr, Shlomo Havlin, and Hern\u00e1n A Makse.","author":"Muchnik Lev","year":"2013","unstructured":"Lev Muchnik , Sen Pei , Lucas C Parra , Saulo DS Reis , Jos\u00e9 S Andrade Jr, Shlomo Havlin, and Hern\u00e1n A Makse. 2013 . Origins of power-law degree distribution in the heterogeneity of human activity in social networks. Scientific reports 3 (2013), 1783. Lev Muchnik, Sen Pei, Lucas C Parra, Saulo DS Reis, Jos\u00e9 S Andrade Jr, Shlomo Havlin, and Hern\u00e1n A Makse. 2013. Origins of power-law degree distribution in the heterogeneity of human activity in social networks. Scientific reports 3 (2013), 1783."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2012.6404677"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/3283407"},{"key":"e_1_2_1_48_1","volume-title":"Clustering and preferential attachment in growing networks. Physical review E 64, 2","author":"Newman Mark EJ","year":"2001","unstructured":"Mark EJ Newman . 2001. Clustering and preferential attachment in growing networks. Physical review E 64, 2 ( 2001 ), 025102. Mark EJ Newman. 2001. Clustering and preferential attachment in growing networks. Physical review E 64, 2 (2001), 025102."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488652"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999792.2999890"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2013.788448"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134086"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.60"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46493-0_32"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2068816.2068825"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064025"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.148698"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2019.00277"},{"key":"e_1_2_1_60_1","volume-title":"Garnett (Eds.)","volume":"32","author":"Suresh Ananda Theertha","year":"2019","unstructured":"Ananda Theertha Suresh . 2019 . Differentially Private Anonymized Histograms. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9-Buc, E. Fox, and R . Garnett (Eds.) , Vol. 32 . Curran Associates, Inc., 7971--7981. Ananda Theertha Suresh. 2019. Differentially Private Anonymized Histograms. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. Curran Associates, Inc., 7971--7981."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2991062"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747643"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433471"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.167"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/89.736332"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3134428"},{"key":"e_1_2_1_67_1","doi-asserted-by":"crossref","unstructured":"Han-Sen Zhong Hui Wang Yu-Hao Deng Ming-Cheng Chen Li-Chao Peng Yi-Han Luo Jian Qin Dian Wu Xing Ding Yi Hu etal 2020. Quantum computational advantage using photons. Science 370 6523 (2020) 1460--1463.  Han-Sen Zhong Hui Wang Yu-Hao Deng Ming-Cheng Chen Li-Chao Peng Yi-Han Luo Jian Qin Dian Wu Xing Ding Yi Hu et al. 2020. Quantum computational advantage using photons. Science 370 6523 (2020) 1460--1463.","DOI":"10.1126\/science.abe8770"},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1109\/TIFS.2014.2368363","article-title":"Correlated differential privacy: Hiding information in non-IID data set","volume":"10","author":"Zhu Tianqing","year":"2014","unstructured":"Tianqing Zhu , Ping Xiong , Gang Li , and Wanlei Zhou . 2014 . Correlated differential privacy: Hiding information in non-IID data set . IEEE Transactions on Information Forensics and Security 10 , 2 (2014), 229 -- 242 . Tianqing Zhu, Ping Xiong, Gang Li, and Wanlei Zhou. 2014. Correlated differential privacy: Hiding information in non-IID data set. IEEE Transactions on Information Forensics and Security 10, 2 (2014), 229--242.","journal-title":"IEEE Transactions on Information Forensics and Security"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3446095.3446106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:23:39Z","timestamp":1672226619000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3446095.3446106"}},"subtitle":["an XOR mechanism"],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":67,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.14778\/3446095.3446106"],"URL":"https:\/\/doi.org\/10.14778\/3446095.3446106","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}