{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T01:04:20Z","timestamp":1772240660108,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,16]],"date-time":"2023-01-16T00:00:00Z","timestamp":1673827200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Manage. Inf. Syst."],"published-print":{"date-parts":[[2023,3,31]]},"abstract":"<jats:p>Data collection under<jats:bold>local differential privacy (LDP)<\/jats:bold>has been gradually on the stage. Compared with the implementation of LDP on the single attribute data collection, that on multi-dimensional data faces great challenges as follows: (1)<jats:italic>Communication cost<\/jats:italic>. Multivariate data collection needs to retain the correlations between attributes, which means that more complex privatization mechanisms will result in more communication costs. (2)<jats:italic>Noise scale<\/jats:italic>. More attributes have to share the privacy budget limited by data utility and privacy-preserving level, which means that less privacy budget can be allocated to each of them, resulting in more noise added to the data. In this work, we innovatively reverse the complex multi-dimensional attributes, i.e., the major<jats:italic>negative<\/jats:italic>factor that leads to the above difficulties, to act as a<jats:italic>beneficial<\/jats:italic>factor to improve the efficiency of privacy budget allocation, so as to realize a multi-dimensional data collection under LDP with high comprehensive performance. Specifically, we first present a<jats:bold>Multivariate<\/jats:bold><jats:bold>k-ary Randomized Response (kRR)<\/jats:bold>mechanism, called<jats:bold>Multi-kRR<\/jats:bold>. It applies the RR directly to each attribute to reduce the communication cost. To deal with the impact of a large amount of noise, we propose a Markov-based dynamic privacy budget allocation mechanism Markov-kRR, which determines the present privacy budget (flipping probability) of an attribute related to the state of the previous attributes. Then, we fix the threshold of flipping times in Markov-kRR and propose an improved mechanism called MarkFixed-kRR, which can obtain more optimized utility by choosing the suitable threshold. Finally, extensive experiments demonstrate the efficiency and effectiveness of our proposed methods.<\/jats:p>","DOI":"10.1145\/3569944","type":"journal-article","created":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T11:04:59Z","timestamp":1667041499000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["The Opportunity in Difficulty: A Dynamic Privacy Budget Allocation Mechanism for Privacy-Preserving Multi-dimensional Data Collection"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0391-9376","authenticated-orcid":false,"given":"Xue","family":"Chen","sequence":"first","affiliation":[{"name":"Key Laboratory of Embedded System and Service Computing (Tongji University), Ministry of Education, China and National (Province-Ministry Joint) Collaborative Innovation Center for Financial Network Security, Tongji University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4752-0316","authenticated-orcid":false,"given":"Cheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Key Laboratory of Embedded System and Service Computing (Tongji University), Ministry of Education, China and National (Province-Ministry Joint) Collaborative Innovation Center for Financial Network Security, Tongji University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5092-5437","authenticated-orcid":false,"given":"Qing","family":"Yang","sequence":"additional","affiliation":[{"name":"Key Laboratory of Embedded System and Service Computing (Tongji University), Ministry of Education, China and National (Province-Ministry Joint) Collaborative Innovation Center for Financial Network Security, Tongji University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4946-8977","authenticated-orcid":false,"given":"Teng","family":"Hu","sequence":"additional","affiliation":[{"name":"Key Laboratory of Embedded System and Service Computing (Tongji University), Ministry of Education, China and National (Province-Ministry Joint) Collaborative Innovation Center for Financial Network Security, Tongji University, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0637-9317","authenticated-orcid":false,"given":"Changjun","family":"Jiang","sequence":"additional","affiliation":[{"name":"Key Laboratory of Embedded System and Service Computing (Tongji University), Ministry of Education, China and National (Province-Ministry Joint) Collaborative Innovation Center for Financial Network Security, Tongji University, China"}]}],"member":"320","published-online":{"date-parts":[[2023,1,16]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"139","volume-title":"Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021)","author":"Abrokwa Desiree","year":"2021","unstructured":"Desiree Abrokwa, Shruti Das, Omer Akgul, and Michelle L. Mazurek. 2021. Comparing security and privacy attitudes among US users of different smartphone and smart-speaker platforms. In Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021). 139\u2013158."},{"key":"e_1_3_2_3_2","article-title":"Learning with privacy at scale","year":"2017","unstructured":"Apple. 2017. Learning with privacy at scale. Apple Machine Learning Journal.","journal-title":"Apple Machine Learning Journal"},{"key":"e_1_3_2_4_2","first-page":"16","article-title":"Practical locally private heavy hitters.","volume":"21","author":"Bassily Raef","year":"2020","unstructured":"Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta. 2020. Practical locally private heavy hitters. J. Mach. Learn. Res. 21 (2020), 16\u20131.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746632"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3430195"},{"key":"e_1_3_2_7_2","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Cao Xiaoyu","year":"2021","unstructured":"Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong. 2021. Data poisoning attacks to local differential privacy protocols. In 30th USENIX Security Symposium (USENIX Security 21)."},{"key":"e_1_3_2_8_2","first-page":"535","volume-title":"Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021)","author":"Chandrasekaran Varun","year":"2021","unstructured":"Varun Chandrasekaran, Suman Banerjee, Bilge Mutlu, and Kassem Fawaz. 2021. PowerCut and obfuscator: An exploration of the design space for privacy-preserving interventions for smart speakers. In Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021). 535\u2013552."},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Lin Jerry Cwei Nachiketa Sahoo Gautam Srivastava and Weiping Ding. 2021. Introduction to the Special Issue on Pattern-Driven Mining Analytics and Prediction for Decision Making Part 1. 3 pages.","DOI":"10.1145\/3512468"},{"key":"e_1_3_2_10_2","volume-title":"NIPS","author":"Ding Bolin","year":"2017","unstructured":"Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately. In NIPS."},{"key":"e_1_3_2_11_2","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1109\/FOCS.2013.53","volume-title":"2013 IEEE 54th Annual Symposium on Foundations of Computer Science","author":"Duchi John C.","year":"2013","unstructured":"John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2013. Local privacy and statistical minimax rates. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE, 429\u2013438."},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1515\/popets-2016-0015"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1201\/9780429258411"},{"issue":"7","key":"e_1_3_2_15_2","first-page":"98","article-title":"Machine learning basics","volume":"1","author":"Goodfellow Ian","year":"2016","unstructured":"Ian Goodfellow, Yoshua Bengio, and Aaron Courville. 2016. Machine learning basics. Deep Learning 1, 7 (2016), 98\u2013164.","journal-title":"Deep Learning"},{"key":"e_1_3_2_16_2","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Hu Changhui","year":"2021","unstructured":"Changhui Hu, Jin Li, Zheli Liu, Xiaojie Guo, Yu Wei, Xuan Guang, Grigorios Loukides, and Changyu Dong. 2021. How to make private distributed cardinality estimation practical, and get differential privacy for free. In 30th USENIX Security Symposium (USENIX Security 21)."},{"key":"e_1_3_2_17_2","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Imola Jacob","year":"2021","unstructured":"Jacob Imola, Takao Murakami, and Kamalika Chaudhuri. 2021. Locally differentially private analysis of graph statistics. In 30th USENIX Security Symposium (USENIX Security 21)."},{"key":"e_1_3_2_18_2","first-page":"2436","volume-title":"International Conference on Machine Learning","author":"Kairouz Peter","year":"2016","unstructured":"Peter Kairouz, Keith Bonawitz, and Daniel Ramage. 2016. Discrete distribution estimation under local privacy. In International Conference on Machine Learning. PMLR, 2436\u20132444."},{"key":"e_1_3_2_19_2","article-title":"Extremal mechanisms for local differential privacy","author":"Kairouz Peter","year":"2014","unstructured":"Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2014. Extremal mechanisms for local differential privacy. arXiv preprint arXiv:1407.1338 (2014).","journal-title":"arXiv preprint arXiv:1407.1338"},{"key":"e_1_3_2_20_2","first-page":"99","volume-title":"Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021)","author":"Kariryaa Ankit","year":"2021","unstructured":"Ankit Kariryaa, Gian-Luca Savino, Carolin Stellmacher, and Johannes Sch\u00f6ning. 2021. Understanding Users\u2019 knowledge about the privacy and security of browser extensions. In Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021). 99\u2013118."},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"issue":"41","key":"e_1_3_2_22_2","doi-asserted-by":"crossref","first-page":"eabk3283","DOI":"10.1126\/sciadv.abk3283","article-title":"The use of differential privacy for census data and its impact on redistricting: The case of the 2020 US Census","volume":"7","author":"Kenny Christopher T.","year":"2021","unstructured":"Christopher T. Kenny, Shiro Kuriwaki, Cory McCartan, Evan T. R. Rosenman, Tyler Simko, and Kosuke Imai. 2021. The use of differential privacy for census data and its impact on redistricting: The case of the 2020 US Census. Science Advances 7, 41 (2021), eabk3283.","journal-title":"Science Advances"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3449042"},{"key":"e_1_3_2_24_2","volume-title":"Information Theory Workshop","author":"Makhdoumi A.","year":"2014","unstructured":"A. Makhdoumi, S. Salamatian, N. Fawaz, and M. Medard. 2014. From the information bottleneck to the privacy funnel. In Information Theory Workshop."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/311445"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517310"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3446636"},{"issue":"5","key":"e_1_3_2_28_2","first-page":"965","article-title":"Privacy engineering for the smart micro-grid","volume":"31","author":"Pal Ranjan","year":"2018","unstructured":"Ranjan Pal, Pan Hui, and Viktor Prasanna. 2018. Privacy engineering for the smart micro-grid. IEEE Transactions on Knowledge and Data Engineering 31, 5 (2018), 965\u2013980.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3456876"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978409"},{"issue":"11","key":"e_1_3_2_31_2","doi-asserted-by":"crossref","first-page":"1623","DOI":"10.1109\/TKDE.2009.190","article-title":"From t-closeness-like privacy to postrandomization via information theory","volume":"22","author":"Rebollo-Monedero David","year":"2009","unstructured":"David Rebollo-Monedero, Jordi Forne, and Josep Domingo-Ferrer. 2009. From t-closeness-like privacy to postrandomization via information theory. IEEE Transactions on Knowledge and Data Engineering 22, 11 (2009), 1623\u20131636.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/1499586.1499731"},{"key":"e_1_3_2_33_2","article-title":"LoPub: High-dimensional crowdsourced data publication with local differential privacy","author":"Ren Xuebin","year":"2018","unstructured":"Xuebin Ren, Chia-mu Yu, Weiren Yu, Shusen Yang, Xinyu Yang, Julie A. McCann, and Philip S. Yu. 2018. LoPub: High-dimensional crowdsourced data publication with local differential privacy. IEEE Transactions on Information Forensics and Security (2018).","journal-title":"IEEE Transactions on Information Forensics and Security"},{"issue":"6","key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1109\/TIFS.2013.2253320","article-title":"Utility-privacy tradeoffs in databases: An information-theoretic approach","volume":"8","author":"Sankar L.","year":"2011","unstructured":"L. Sankar, S. R. Rajagopalan, and H. V. Poor. 2011. Utility-privacy tradeoffs in databases: An information-theoretic approach. IEEE Transactions on Information Forensics and Security 8, 6 (2011), 838\u2013852.","journal-title":"IEEE Transactions on Information Forensics and Security"},{"key":"e_1_3_2_35_2","first-page":"573","volume-title":"Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021)","author":"Tahaei Mohammad","year":"2021","unstructured":"Mohammad Tahaei, Alisa Frik, Kami Vaniea, and Design Informatics. 2021. Deciding on personalized ads: Nudging developers about user privacy. In Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021). 573\u2013596."},{"issue":"9","key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"3486","DOI":"10.1109\/TITS.2018.2877059","article-title":"Estimating travel speed of a road section through sparse crowdsensing data","volume":"20","author":"Wang Cheng","year":"2018","unstructured":"Cheng Wang, Zhiyang Xie, Lu Shao, Zhenzhen Zhang, and MengChu Zhou. 2018. Estimating travel speed of a road section through sparse crowdsensing data. IEEE Transactions on Intelligent Transportation Systems 20, 9 (2018), 3486\u20133495.","journal-title":"IEEE Transactions on Intelligent Transportation Systems"},{"key":"e_1_3_2_37_2","article-title":"Mutual information optimally local private discrete distribution estimation","author":"Wang Shaowei","year":"2016","unstructured":"Shaowei Wang, Liusheng Huang, Pengzhan Wang, Yiwen Nie, Hongli Xu, Wei Yang, Xiang-Yang Li, and Chunming Qiao. 2016. Mutual information optimally local private discrete distribution estimation. arXiv preprint arXiv:1607.08025 (2016).","journal-title":"arXiv preprint arXiv:1607.08025"},{"key":"e_1_3_2_38_2","first-page":"729","volume-title":"26th USENIX Security Symposium (USENIX Security 17)","author":"Wang Tianhao","year":"2017","unstructured":"Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium (USENIX Security 17). 729\u2013745."},{"key":"e_1_3_2_39_2","article-title":"Locally differentially private heavy hitter identification","author":"Wang Tianhao","year":"2019","unstructured":"Tianhao Wang, Ninghui Li, and Somesh Jha. 2019. Locally differentially private heavy hitter identification. IEEE Transactions on Dependable and Secure Computing (2019).","journal-title":"IEEE Transactions on Dependable and Secure Computing"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_3_2_41_2","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1145\/3243734.3243742","volume-title":"Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security","author":"Zhang Zhikun","year":"2018","unstructured":"Zhikun Zhang, Tianhao Wang, Ninghui Li, Shibo He, and Jiming Chen. 2018. CALM: Consistent adaptive local marginal for marginal release under local differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 212\u2013229."},{"key":"e_1_3_2_42_2","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Zhang Zhikun","year":"2021","unstructured":"Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. 2021. PrivSyn: Differentially private data synthesis. In 30th USENIX Security Symposium (USENIX Security 21)."},{"key":"e_1_3_2_43_2","first-page":"197","volume-title":"Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021)","author":"Zhang-Kennedy Leah","year":"2021","unstructured":"Leah Zhang-Kennedy and Sonia Chiasson. 2021. \u201cWhether it\u2019s moral is a whole other story\u201d: Consumer perspectives on privacy regulations and corporate data practices. In Seventeenth Symposium on Usable Privacy and Security (SOUPS 2021). 197\u2013216."}],"container-title":["ACM Transactions on Management Information Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569944","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3569944","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:07:51Z","timestamp":1750183671000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3569944"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,16]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3,31]]}},"alternative-id":["10.1145\/3569944"],"URL":"https:\/\/doi.org\/10.1145\/3569944","relation":{},"ISSN":["2158-656X","2158-6578"],"issn-type":[{"value":"2158-656X","type":"print"},{"value":"2158-6578","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,16]]},"assertion":[{"value":"2022-04-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}