{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:40:02Z","timestamp":1755906002184,"version":"3.44.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>\n            Protecting sensitive information on data streams is a pivotal challenge for modern systems. Current approaches to providing privacy in data streams can be broadly categorized into two strategies. The first strategy involves transforming the stream into a private sequence of values, enabling the subsequent use of non-private methods of analysis. While effective, this approach incurs high memory costs, often proportional to the size of the database. Alternatively, a compact data structure can be used to provide a private summary of the stream. However, these data structures are limited to predefined queries, restricting their flexibility. To overcome these limitations, we propose a lightweight synthetic data generator, PrivHP, that provides differential privacy guarantees. PrivHP is based on a novel method for the private hierarchical decomposition of the input domain in bounded memory. As the decomposition approximates the cumulative distribution function of the input, it serves as a lightweight structure for synthetic data generation. PrivHP is the first method to provide a principled trade-off between accuracy and space for private hierarchical decompositions. It achieves this by balancing hierarchy depth, noise addition, and selective pruning of low-frequency subdomains while preserving high-frequency ones, all identified in a privacy-preserving manner. To ensure memory efficiency, we employ private sketches to estimate subdomain frequencies without accessing the entire dataset. Central to our approach is the introduction of a pruning parameter\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            , which enables an almost smooth interpolation between space usage and utility, and a measure of skew tail\n            <jats:sub>k<\/jats:sub>\n            , which is a vector of subdomain frequencies containing all but the largest\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            coordinates. PrivHP processes a dataset\n            <jats:italic toggle=\"yes\">X<\/jats:italic>\n            using\n            <jats:italic toggle=\"yes\">M<\/jats:italic>\n            =\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (k log\n            <jats:sup>2<\/jats:sup>\n            |\n            <jats:italic toggle=\"yes\">X<\/jats:italic>\n            |)) space and, on input domain \u03a9 = [0,1]\n            <jats:sup>d<\/jats:sup>\n            , while maintaining \u03b5-differential privacy, produces a synthetic data generator that is at distance\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (\n            <jats:italic toggle=\"yes\">M<\/jats:italic>\n            <jats:sup>(1-1\/d)<\/jats:sup>\n            \/\u03b5\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            + ||tail\n            <jats:sub>k<\/jats:sub>\n            (\n            <jats:italic toggle=\"yes\">X<\/jats:italic>\n            )||\n            <jats:sub>1<\/jats:sub>\n            \/M\n            <jats:sup>1\/d<\/jats:sup>\n            <jats:italic toggle=\"yes\">n<\/jats:italic>\n            ) from the empirical distribution in the expected Wasserstein metric. Compared to the state-of-the-art, PMM, which achieves accuracy\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            ((\u03b5 n)\n            <jats:sup>-1\/d<\/jats:sup>\n            ) with memory\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (\u03b5 n), our method introduces an additional approximation error term of\n            <jats:italic toggle=\"yes\">O<\/jats:italic>\n            (||tail\n            <jats:sub>k<\/jats:sub>\n            (\n            <jats:italic toggle=\"yes\">X<\/jats:italic>\n            )||\n            <jats:sub>1<\/jats:sub>\n            \/(M\n            <jats:sup>1\/d<\/jats:sup>\n            n)), but operates in significantly reduced space. Additionally, we provide interpretable utility bounds that account for all error sources, including those introduced by the fixed hierarchy depth, privacy noise, hierarchy pruning, and frequency approximations.\n          <\/jats:p>","DOI":"10.1145\/3725244","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Private Synthetic Data Generation in Bounded Memory"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6661-8258","authenticated-orcid":false,"given":"Rayne","family":"Holland","sequence":"first","affiliation":[{"name":"CSIRO's Data61, Melbourne, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6353-8359","authenticated-orcid":false,"given":"Seyit","family":"Camtepe","sequence":"additional","affiliation":[{"name":"CSIRO's Data61, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3855-3378","authenticated-orcid":false,"given":"Chandra","family":"Thapa","sequence":"additional","affiliation":[{"name":"CSIRO's Data61, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5411-5039","authenticated-orcid":false,"given":"Minhui","family":"Xue","sequence":"additional","affiliation":[{"name":"CSIRO's Data61, Adelaide, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Daniel Alabi Omri Ben-Eliezer and Anamay Chaturvedi. 2022. Bounded space differentially private quantiles. arXiv preprint arXiv:2201.03380 (2022)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265569"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695826"},{"key":"e_1_2_1_4_1","volume-title":"Szemeredi regularity, and differential privacy. arXiv preprint arXiv:2301.02705","author":"Boedihardjo March","year":"2023","unstructured":"March Boedihardjo, Thomas Strohmer, and Roman Vershynin. 2023. Covariance loss, Szemeredi regularity, and differential privacy. arXiv preprint arXiv:2301.02705, (2023)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"March Boedihardjo Thomas Strohmer and Roman Vershynin. 2024. Private measures random walks and synthetic data. Probability theory and related fields (2024) 1-43.","DOI":"10.1007\/s00440-024-01279-z"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134102"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972931.14"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9678-x"},{"key":"e_1_2_1_11_1","first-page":"211","volume-title":"Foundations and Trends\u00ae in Theoretical Computer Science","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork, Aaron Roth, et al., 2014. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science, Vol. 9, 3-4 (2014), 211-407."},{"key":"e_1_2_1_12_1","volume-title":"Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong.","author":"Epasto Alessandro","year":"2023","unstructured":"Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. 2023. Differentially private continual releases of streaming frequency moment estimations. arXiv preprint arXiv:2301.05605, (2023)."},{"key":"e_1_2_1_13_1","unstructured":"Michael Hay Vibhor Rastogi Gerome Miklau and Dan Suciu. 2009. Boosting the accuracy of differentially-private histograms through consistency. arXiv preprint arXiv:0904.0942 (2009)."},{"key":"e_1_2_1_14_1","unstructured":"Yiyun He Thomas Strohmer Roman Vershynin and Yizhe Zhu. 2023a. Differentially private low-dimensional representation of high-dimensional data. arXiv preprint arXiv:2305.17148 (2023)."},{"key":"e_1_2_1_15_1","volume-title":"The Thirty Sixth Annual Conference on Learning Theory. PMLR, 3941-3968","author":"He Yiyun","year":"2023","unstructured":"Yiyun He, Roman Vershynin, and Yizhe Zhu. 2023b. Algorithmically effective differentially private synthetic data. In The Thirty Sixth Annual Conference on Learning Theory. PMLR, 3941-3968."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_2_1_17_1","unstructured":"Girish Kumar Thomas Strohmer and Roman Vershynin. 2024. PrivStream: An Algorithm for Streaming Differentially Private Data. arXiv preprint arXiv:2401.14577 (2024)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588673"},{"key":"e_1_2_1_19_1","first-page":"690","article-title":"Iterative methods for private synthetic data: Unifying framework and new methods","volume":"34","author":"Liu Terrance","year":"2021","unstructured":"Terrance Liu, Giuseppe Vietri, and Steven Z Wu. 2021. Iterative methods for private synthetic data: Unifying framework and new methods. Advances in Neural Information Processing Systems, Vol. 34 (2021), 690-702.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_20_1","volume-title":"International Conference on Machine Learning. PMLR, 15484-15500","author":"Meunier Laurent","year":"2022","unstructured":"Laurent Meunier, Blaise J Delattre, Alexandre Araujo, and Alexandre Allauzen. 2022. A dynamical system perspective for lipschitz neural networks. In International Conference on Machine Learning. PMLR, 15484-15500."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1143-1160","author":"Monemizadeh Morteza","year":"2010","unstructured":"Morteza Monemizadeh and David P Woodruff. 2010. 1-pass relative error lp-samplers with applications. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 1143-1160."},{"key":"e_1_2_1_22_1","first-page":"25631","article-title":"Improved utility analysis of private countsketch","volume":"35","author":"Pagh Rasmus","year":"2022","unstructured":"Rasmus Pagh and Mikkel Thorup. 2022. Improved utility analysis of private countsketch. Advances in Neural Information Processing Systems, Vol. 35 (2022), 25631-25643.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_23_1","volume-title":"Hassan Jameel Asghar, and Dali Kaafar","author":"Perrier Victor","year":"2018","unstructured":"Victor Perrier, Hassan Jameel Asghar, and Dali Kaafar. 2018. Private continual release of real-valued data streams. arXiv preprint arXiv:1811.03197, (2018)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556576"},{"volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Thaler Justin","key":"e_1_2_1_25_1","unstructured":"Justin Thaler, Jonathan Ullman, and Salil Vadhan. 2012. Faster algorithms for privately releasing marginals. In International Colloquium on Automata, Languages, and Programming. Springer, 810-821."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19571-6_24"},{"key":"e_1_2_1_27_1","first-page":"18282","article-title":"Private synthetic data for multitask learning and marginal queries","volume":"35","author":"Vietri Giuseppe","year":"2022","unstructured":"Giuseppe Vietri, Cedric Archambeau, Sergul Aydore, William Brown, Michael Kearns, Aaron Roth, Ankit Siva, Shuai Tang, and Steven Z Wu. 2022. Private synthetic data for multitask learning and marginal queries. Advances in Neural Information Processing Systems, Vol. 35 (2022), 18282-18295.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_28_1","first-page":"669","article-title":"Distance-Based Classification with Lipschitz Functions","volume":"5","author":"von Luxburg Ulrike","year":"2004","unstructured":"Ulrike von Luxburg and Olivier Bousquet. 2004. Distance-Based Classification with Lipschitz Functions. J. Mach. Learn. Res., Vol. 5, Jun (2004), 669-695.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484750"},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"Differentially private data releasing for smooth queries","volume":"17","author":"Wang Ziteng","year":"2016","unstructured":"Ziteng Wang, Chi Jin, Kai Fan, Jiaqi Zhang, Junliang Huang, Yiqiao Zhong, and Liwei Wang. 2016. Differentially private data releasing for smooth queries. Journal of Machine Learning Research, Vol. 17, 51 (2016), 1-42.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2999580"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882928"},{"key":"e_1_2_1_33_1","first-page":"12691","article-title":"Differentially private linear sketches: Efficient implementations and applications","volume":"35","author":"Zhao Fuheng","year":"2022","unstructured":"Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. 2022. Differentially private linear sketches: Efficient implementations and applications. Advances in Neural Information Processing Systems, Vol. 35 (2022), 12691-12704.","journal-title":"Advances in Neural Information Processing Systems"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725244","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:17:47Z","timestamp":1755904667000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725244"],"URL":"https:\/\/doi.org\/10.1145\/3725244","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}