{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:20Z","timestamp":1779174800098,"version":"3.51.4"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T00:00:00Z","timestamp":1701993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972309, 62272369, 62206207"],"award-info":[{"award-number":["61972309, 62272369, 62206207"]}],"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":[[2023,12,8]]},"abstract":"<jats:p>Star-join query is the fundamental task in data warehouse and has wide applications in On-line Analytical Processing (olap) scenarios. Due to the large number of foreign key constraints and the asymmetric effect in the neighboring instance between the fact and dimension tables, even those latest dp efforts specifically designed for join, if directly applied to star-join query, will suffer from extremely large estimation errors and expensive computational cost. In this paper, we are thus motivated to propose DP-starJ, a novel Differentially Private framework for star-Join queries. DP-starJ consists of a series of strategies tailored to specific features of star-join, including 1) we unveil the different effects of fact and dimension tables on the neighboring database instances, and accordingly revisit the definitions tailored to different cases of star-join; 2) we propose Predicate Mechanism (PM), which utilizes predicate perturbation to inject noise into the join procedure instead of the results; 3) to further boost the robust performance, we propose a dp-compliant star-join algorithm for various types of star-join tasks based on PM. We provide both theoretical analysis and empirical study, which demonstrate the superiority of the proposed methods over the state-of-the-art solutions in terms of accuracy, efficiency, and scalability.<\/jats:p>","DOI":"10.1145\/3626725","type":"journal-article","created":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T14:01:21Z","timestamp":1702389681000},"page":"1-24","source":"Crossref","is-referenced-by-count":2,"title":["DP-starJ: A Differential Private Scheme towards Analytical Star-Join Queries"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-4768-8458","authenticated-orcid":false,"given":"Congcong","family":"Fu","sequence":"first","affiliation":[{"name":"Xidian University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2382-6289","authenticated-orcid":false,"given":"Hui","family":"Li","sequence":"additional","affiliation":[{"name":"Xidian University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4110-2068","authenticated-orcid":false,"given":"Jian","family":"Lou","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-5789-1390","authenticated-orcid":false,"given":"Huizhen","family":"Li","sequence":"additional","affiliation":[{"name":"Xidian University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5569-0780","authenticated-orcid":false,"given":"Jiangtao","family":"Cui","sequence":"additional","affiliation":[{"name":"Xidian University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"Myrto Arapinis Diego Figueira and Marco Gaboardi. 2016. Sensitivity of counting queries. In International Colloquium on Automata Languages and Programming (ICALP)."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265569"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.152"},{"key":"e_1_2_2_4_1","volume-title":"PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy. arXiv preprint arXiv:2304.04545","author":"Cai Kuntai","year":"2023","unstructured":"Kuntai Cai, Xiaokui Xiao, and Graham Cormode. 2023. PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy. arXiv preprint arXiv:2304.04545 (2023)."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2926745"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452813"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524143"},{"key":"e_1_2_2_10_1","volume-title":"33rd International Colloquium, ICALP 2006, Venice, Italy, July 10--14, 2006, Proceedings, Part II 33","author":"Dwork Cynthia","year":"2006","unstructured":"Cynthia Dwork. 2006. Differential privacy. In Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10--14, 2006, Proceedings, Part II 33. Springer, 1--12."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_2_12_1","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_2_13_1","unstructured":"Congcong Fu Hui Li Jian Lou and Jiangtao Cui. 2023. A Differential Private Scheme towards Analytical Star-Join Queries. Technical Report. http:\/\/arxiv.org\/abs\/2310.04711."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497528"},{"key":"e_1_2_2_15_1","volume-title":"A simple and practical algorithm for differentially private data release. Advances in neural information processing systems","author":"Hardt Moritz","year":"2012","unstructured":"Moritz Hardt, Katrina Ligett, and Frank McSherry. 2012. A simple and practical algorithm for differentially private data release. Advances in neural information processing systems, Vol. 25 (2012)."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_2_18_1","volume-title":"Seng Pei Liew, and Masatoshi Yoshikawa","author":"Kato Fumiyuki","year":"2022","unstructured":"Fumiyuki Kato, Tsubasa Takahashi, Shun Takagi, Yang Cao, Seng Pei Liew, and Masatoshi Yoshikawa. 2022. HDPView: Differentially Private Materialized View for Exploring High Dimensional Relational Data. arXiv preprint arXiv:2203.06791 (2022)."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342274"},{"key":"e_1_2_2_20_1","unstructured":"Jure Leskovec and Andrej Krevl. 2016. SNAP datasets: Stanford large network dataset collection(2014). http:\/\/snap.stanford.edu\/data"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0398-x"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526162"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_2_2_24_1","volume-title":"Presented as part of the 10th $$USENIX$$ Symposium on Operating Systems Design and Implementation ($$OSDI$$ 12). 149--162.","author":"Narayan Arjun","unstructured":"Arjun Narayan and Andreas Haeberlen. 2012. DJoin: Differentially private join queries over distributed databases. In Presented as part of the 10th $$USENIX$$ Symposium on Operating Systems Design and Implementation ($$OSDI$$ 12). 149--162."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488652"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10424-4_17"},{"key":"e_1_2_2_28_1","first-page":"50","article-title":"The star schema benchmark (SSB)","volume":"200","author":"O'Neil Patrick E","year":"2007","unstructured":"Patrick E O'Neil, Elizabeth J O'Neil, and Xuedong Chen. 2007. The star schema benchmark (SSB). Pat, Vol. 200, 0 (2007), 50.","journal-title":"Pat"},{"key":"e_1_2_2_29_1","volume-title":"Differential privacy for relational algebra: Improving the sensitivity bounds via constraint systems. arXiv preprint arXiv:1207.0872","author":"Palamidessi Catuscia","year":"2012","unstructured":"Catuscia Palamidessi and Marco Stronati. 2012. Differential privacy for relational algebra: Improving the sensitivity bounds via constraint systems. arXiv preprint arXiv:1207.0872 (2012)."},{"key":"e_1_2_2_30_1","volume-title":"Calibrating data to sensitivity in private data analysis. arXiv preprint arXiv:1203.3453","author":"Proserpio Davide","year":"2012","unstructured":"Davide Proserpio, Sharon Goldberg, and Frank McSherry. 2012. Calibrating data to sensitivity in private data analysis. arXiv preprint arXiv:1203.3453 (2012)."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556576"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588575"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46439-5_18"},{"key":"e_1_2_2_34_1","volume-title":"A review of star schema benchmark. arXiv preprint arXiv:1606.00295","author":"Sanchez Jimi","year":"2016","unstructured":"Jimi Sanchez. 2016. A review of star schema benchmark. arXiv preprint arXiv:1606.00295 (2016)."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00022"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_2_2_37_1","volume-title":"Locally differentially private frequency estimation with consistency. arXiv preprint arXiv:1905.08320","author":"Wang Tianhao","year":"2019","unstructured":"Tianhao Wang, Milan Lopuha\"a-Zwakenberg, Zitao Li, Boris Skoric, and Ninghui Li. 2019. Locally differentially private frequency estimation with consistency. arXiv preprint arXiv:1905.08320 (2019)."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2020-0025"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.247"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0309-y"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699501"},{"key":"e_1_2_2_42_1","volume-title":"A neural database for differentially private spatial range queries. arXiv preprint arXiv:2108.01496","author":"Zeighami Sepanta","year":"2021","unstructured":"Sepanta Zeighami, Ritesh Ahuja, Gabriel Ghinita, and Cyrus Shahabi. 2021. A neural database for differentially private spatial range queries. arXiv preprint arXiv:2108.01496 (2021)."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.68"},{"key":"e_1_2_2_44_1","volume-title":"Secure Shapley Value for Cross-Silo Federated Learning. arXiv preprint arXiv:2209.04856","author":"Zheng Shuyuan","year":"2022","unstructured":"Shuyuan Zheng, Yang Cao, and Masatoshi Yoshikawa. 2022. Secure Shapley Value for Cross-Silo Federated Learning. arXiv preprint arXiv:2209.04856 (2022)."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626725","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3626725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T13:01:11Z","timestamp":1755867671000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3626725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,8]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,8]]}},"alternative-id":["10.1145\/3626725"],"URL":"https:\/\/doi.org\/10.1145\/3626725","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,8]]}}}