{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T15:53:26Z","timestamp":1783439606051,"version":"3.54.6"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,4]]},"abstract":"<jats:p>\n            Most user-generated data in online services are presented as set-valued data, e.g., visited website URLs, recently used Apps by a person, and etc. These data are of great value to service providers, but also bring privacy concerns if collected and analyzed directly. To tackle potential privacy threatens, local differential privacy (LDP) attracts increasing attention nowadays. However, existing approaches only provide sub-optimal error bound for set-valued data distribution estimation with LDP. Besides, it is computational expensive and communication expensive to use for high dimensional set-valued data, considering large domains in real scenarios. Thus, existing approaches are unpractical to use on resource-constrained user-side devices (e.g., smartphones and wearable devices). In this paper, we propose a utility-optimal and efficient set-valued data publication method (i.e.,\n            <jats:italic>wheel mechanism<\/jats:italic>\n            ). On the user side, each user contributes only one numerical value to represent their privatized data. The computational complexity is\n            <jats:italic>O<\/jats:italic>\n            (min{\n            <jats:italic>m<\/jats:italic>\n            log\n            <jats:italic>m<\/jats:italic>\n            ,\n            <jats:italic>me<\/jats:italic>\n            <jats:sup>\u025b<\/jats:sup>\n            }) and communication cost is\n            <jats:italic>O<\/jats:italic>\n            (log(\n            <jats:italic>me<\/jats:italic>\n            <jats:sup>\u025b<\/jats:sup>\n            )) bits, while existing approaches usually depend on\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>d<\/jats:italic>\n            ) or\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>d<\/jats:italic>\n            ), where\n            <jats:italic>m<\/jats:italic>\n            is the number of items in the set-valued data (\n            <jats:italic>m<\/jats:italic>\n            \u2261 1 for categorical data),\n            <jats:italic>d<\/jats:italic>\n            is the domain size (usually\n            <jats:italic>d<\/jats:italic>\n            \u226b\n            <jats:italic>m<\/jats:italic>\n            ) and \u025b is the privacy budget. On the server side, the estimator takes numerical values from users as input and derives an unbiased distribution estimation. Theoretical results show that estimation error bounds are improved from previously known [EQUATION] to the optimal rate [EQUATION]. Results on extensive experiments demonstrate that our proposed wheel mechanism is 3-100\u00d7 faster than existing approaches, meanwhile has optimal statistical efficiency.\n          <\/jats:p>","DOI":"10.14778\/3389133.3389140","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T19:28:19Z","timestamp":1588620499000},"page":"1234-1247","source":"Crossref","is-referenced-by-count":23,"title":["Set-valued data publication with local privacy"],"prefix":"10.14778","volume":"13","author":[{"given":"Shaowei","family":"Wang","sequence":"first","affiliation":[{"name":"Tencent Games"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuqiu","family":"Qian","sequence":"additional","affiliation":[{"name":"Tencent Games"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiachun","family":"Du","sequence":"additional","affiliation":[{"name":"Tencent Games"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Yang","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Liusheng","family":"Huang","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongli","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,5,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Hadamard response: Estimating distributions privately, efficiently, and with little communication. arXiv preprint arXiv:1802.04705","author":"Acharya J.","year":"2018","unstructured":"J. Acharya , Z. Sun , and H. Zhang . Hadamard response: Estimating distributions privately, efficiently, and with little communication. arXiv preprint arXiv:1802.04705 , 2018 . J. Acharya, Z. Sun, and H. Zhang. Hadamard response: Estimating distributions privately, efficiently, and with little communication. arXiv preprint arXiv:1802.04705, 2018."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746632"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402744"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196906"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274608"},{"key":"e_1_2_1_6_1","volume-title":"Differentially private publication of sparse data. arXiv preprint arXiv:1103.0825","author":"Cormode G.","year":"2011","unstructured":"G. Cormode , M. Procopiuc , D. Srivastava , and T. T. Tran . Differentially private publication of sparse data. arXiv preprint arXiv:1103.0825 , 2011 . G. Cormode, M. Procopiuc, D. Srivastava, and T. T. Tran. Differentially private publication of sparse data. arXiv preprint arXiv:1103.0825, 2011."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01957-9_8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14577-3_13"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070481.2070550"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2017.1389735"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1791834.1791836"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1515\/popets-2016-0015"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359553"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497480"},{"key":"e_1_2_1_17_1","volume-title":"Santa Clara Univ. Legal Studies Research Paper","author":"Goldman E.","year":"2019","unstructured":"E. Goldman . An introduction to the california consumer privacy act (ccpa) . Santa Clara Univ. Legal Studies Research Paper , 2019 . E. Goldman. An introduction to the california consumer privacy act (ccpa). Santa Clara Univ. Legal Studies Research Paper, 2019."},{"key":"e_1_2_1_18_1","volume-title":"Wired (June 13, 2016","author":"Greenberg A.","year":"2016","unstructured":"A. Greenberg . Apple's ` differential privacy'is about collecting your data--but not your data . Wired (June 13, 2016 ), 2016 . A. Greenberg. Apple's `differential privacy'is about collecting your data--but not your data. Wired (June 13, 2016), 2016."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/PerCom.2012.6199861"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956815"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687733"},{"key":"e_1_2_1_22_1","volume-title":"NDSS","author":"Huang Y.","year":"2012","unstructured":"Y. Huang , D. Evans , and J. Katz . Private set intersection: Are garbled circuits better than custom protocols ? In NDSS , 2012 . Y. Huang, D. Evans, and J. Katz. Private set intersection: Are garbled circuits better than custom protocols? In NDSS, 2012."},{"key":"e_1_2_1_23_1","first-page":"2436","volume-title":"International Conference on Machine Learning","author":"Kairouz P.","year":"2016","unstructured":"P. Kairouz , K. Bonawitz , and D. Ramage . Discrete distribution estimation under local privacy . In International Conference on Machine Learning , pages 2436 -- 2444 , 2016 . P. Kairouz, K. Bonawitz, and D. Ramage. Discrete distribution estimation under local privacy. In International Conference on Machine Learning, pages 2436--2444, 2016."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350251"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4018\/978-1-59140-557-3.ch189"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978409"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218488502001648"},{"key":"e_1_2_1_29_1","volume-title":"Privacy loss in apple's implementation of differential privacy on macos 10.12. arXiv preprint arXiv:1709.02753","author":"Tang J.","year":"2017","unstructured":"J. Tang , A. Korolova , X. Bai , X. Wang , and X. Wang . Privacy loss in apple's implementation of differential privacy on macos 10.12. arXiv preprint arXiv:1709.02753 , 2017 . J. Tang, A. Korolova, X. Bai, X. Wang, and X. Wang. Privacy loss in apple's implementation of differential privacy on macos 10.12. arXiv preprint arXiv:1709.02753, 2017."},{"key":"e_1_2_1_30_1","first-page":"63","article-title":"Privacy in the age of big data: a time for big decisions","volume":"64","author":"Tene O.","year":"2011","unstructured":"O. Tene and J. Polonetsky . Privacy in the age of big data: a time for big decisions . Stan. L. Rev. Online , 64 : 63 , 2011 . O. Tene and J. Polonetsky. Privacy in the age of big data: a time for big decisions. Stan. L. Rev. Online, 64:63, 2011.","journal-title":"Stan. L. Rev. Online"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453874"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/3152676"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8486234"},{"key":"e_1_2_1_34_1","volume-title":"Mutual information optimally local private discrete distribution estimation. arXiv preprint arXiv:1607.08025","author":"Wang S.","year":"2016","unstructured":"S. Wang , L. Huang , P. Wang , Y. Nie , H. Xu , W. Yang , X.-Y. Li , and C. Qiao . Mutual information optimally local private discrete distribution estimation. arXiv preprint arXiv:1607.08025 , 2016 . S. Wang, L. Huang, P. Wang, Y. Nie, H. Xu, W. Yang, X.-Y. Li, and C. Qiao. Mutual information optimally local private discrete distribution estimation. arXiv preprint arXiv:1607.08025, 2016."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2017.8056977"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/3241189.3241247"},{"key":"e_1_2_1_37_1","volume-title":"Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. arXiv preprint arXiv:1309.1541","author":"Wang W.","year":"2013","unstructured":"W. Wang and M. A. Carreira-Perpinan . Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. arXiv preprint arXiv:1309.1541 , 2013 . W. Wang and M. A. Carreira-Perpinan. Projection onto the probability simplex: An efficient algorithm with a simple proof, and an application. arXiv preprint arXiv:1309.1541, 2013."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2809790"},{"key":"e_1_2_1_39_1","first-page":"423","volume-title":"Festschrift for Lucien Le Cam","author":"Assouad B. Yu.","year":"1997","unstructured":"B. Yu. Assouad , fano, and le cam . In Festschrift for Lucien Le Cam , pages 423 -- 435 . Springer , 1997 . B. Yu. Assouad, fano, and le cam. In Festschrift for Lucien Le Cam, pages 423--435. Springer, 1997."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/2428536.2428539"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3389133.3389140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:17:25Z","timestamp":1672226245000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3389133.3389140"}},"subtitle":["tight error bounds and efficient mechanisms"],"short-title":[],"issued":{"date-parts":[[2020,4]]},"references-count":40,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["10.14778\/3389133.3389140"],"URL":"https:\/\/doi.org\/10.14778\/3389133.3389140","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,4]]}}}