{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:16:09Z","timestamp":1768108569032,"version":"3.49.0"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T00:00:00Z","timestamp":1717027200000},"content-version":"vor","delay-in-days":1,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Cisco","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Packard Fellowship"},{"name":"HKRGC","award":["16205420, 16205422, and 16204223"],"award-info":[{"award-number":["16205420, 16205422, and 16204223"]}]},{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2128519 and 2044679"],"award-info":[{"award-number":["2128519 and 2044679"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ONR"},{"name":"SRI","award":["DARPA SIEVE program"],"award-info":[{"award-number":["DARPA SIEVE program"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>The problem of continual observation under differential privacy has been studied extensively in the literature. However, all existing works, with the exception of [28,51], have only studied the simple counting query and its derivatives. Join queries, which are arguably the most important class of queries in relational databases, have only been considered in [28,51], but the solutions offered there have two limitations: First, they only support a few specific graph pattern queries, which are special cases of joins. Second, they require hard degree\/frequency constraints on the graph\/database instance, and the privatized query answers have errors proportional to these constraints.<\/jats:p>\n          <jats:p>In this paper, we propose a new differentially private mechanism for continual observation of joins that overcomes these two limitations. Our mechanism supports arbitrary joins and predicates, and do not require any constraints to be given in advance, even over an infinite stream. More importantly, it yields an error that is proportional to the actual maximum degree\/frequencies in the graph\/database instance at the current time of observation. Such an instance-specific utility guarantee is much preferred for the continual observation problem, where the database size and the query answer may change significantly over time.<\/jats:p>","DOI":"10.1145\/3654931","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-27","source":"Crossref","is-referenced-by-count":9,"title":["Continual Observation of Joins under Differential Privacy"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0394-4125","authenticated-orcid":false,"given":"Wei","family":"Dong","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-9922-2377","authenticated-orcid":false,"given":"Zijun","family":"Chen","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4167-8670","authenticated-orcid":false,"given":"Qiyao","family":"Luo","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5605-1048","authenticated-orcid":false,"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2178-3716","authenticated-orcid":false,"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Foundations of databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of databases. Vol. 8. Addison-Wesley Reading."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_3_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_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448496.2448530"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589287"},{"key":"e_1_2_1_7_1","volume-title":"The Bulletin of the Technical Committee on Data Engineering","volume":"38","author":"Carbone Paris","year":"2015","unstructured":"Paris Carbone, Asterios Katsifodimos, Stephan Ewen, Volker Markl, Seif Haridi, and Kostas Tzoumas. 2015. Apache flink: Stream and batch processing in a single engine. The Bulletin of the Technical Committee on Data Engineering, Vol. 38, 4 (2015)."},{"key":"e_1_2_1_8_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 2397--2419","author":"Cardoso Adrian Rivera","year":"2022","unstructured":"Adrian Rivera Cardoso and Ryan Rogers. 2022. Differentially private histograms under continual observation: Streaming selection into the unknown. In International Conference on Artificial Intelligence and Statistics. PMLR, 2397--2419."},{"key":"e_1_2_1_9_1","volume-title":"International Symposium on Privacy Enhancing Technologies Symposium. Springer, 140--159","author":"Hubert Chan T-H","year":"2012","unstructured":"T-H Hubert Chan, Mingfei Li, Elaine Shi, and Wenchang Xu. 2012. Differentially private continual monitoring of heavy hitters from distributed streams. In International Symposium on Privacy Enhancing Technologies Symposium. Springer, 140--159."},{"key":"e_1_2_1_10_1","volume-title":"Private and Continual Release of Statistics. ACM Transactions on Information and System Security","author":"Hubert Chan T.-H.","year":"2011","unstructured":"T.-H. Hubert Chan, Elaine Shi, and Dawn Song. 2011. Private and Continual Release of Statistics. ACM Transactions on Information and System Security (2011)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735503"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134102"},{"key":"e_1_2_1_14_1","volume-title":"Advances in Neural Information Processing Systems","volume":"31","author":"Cummings Rachel","year":"2018","unstructured":"Rachel Cummings, Sara Krehbiel, Kevin A Lai, and Uthaipon Tantipongpipat. 2018. Differential privacy for growing databases. Advances in Neural Information Processing Systems, Vol. 31 (2018)."},{"key":"e_1_2_1_15_1","unstructured":"Sergey Denisov Brendan McMahan Keith Rush Adam Smith and Abhradeep Thakurta. 2022. Improved differential privacy for sgd via optimal private linear operators on adaptive streams. In NeurIPS."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46215.2023.10179466"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589268"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452813"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524143"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3631504.3631506"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588669"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806787"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48800-3_30"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536467"},{"key":"e_1_2_1_26_1","volume-title":"Foundations and Trends\u00ae in Theoretical Computer Science","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork and Aaron Roth. 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_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560567"},{"key":"e_1_2_1_28_1","volume-title":"Differentially Private Algorithms for Graphs Under Continual Observation. In 29th Annual European Symposium on Algorithms (ESA","author":"Fichtenberger Hendrik","year":"2021","unstructured":"Hendrik Fichtenberger, Monika Henzinger, and Wolfgang Ost. 2021. Differentially Private Algorithms for Graphs Under Continual Observation. In 29th Annual European Symposium on Algorithms (ESA 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"key":"e_1_2_1_30_1","volume-title":"Constant matters: Fine-grained Complexity of Differentially Private Continual Observation Using Completely Bounded Norms. arXiv preprint arXiv:2202.11205","author":"Henzinger Monika","year":"2022","unstructured":"Monika Henzinger and Jalaj Upadhyay. 2022. Constant matters: Fine-grained Complexity of Differentially Private Continual Observation Using Completely Bounded Norms. arXiv preprint arXiv:2202.11205 (2022)."},{"key":"e_1_2_1_31_1","volume-title":"Almost tight error bounds on differentially private continual counting. arXiv preprint arXiv:2211.05006","author":"Henzinger Monika","year":"2022","unstructured":"Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. 2022. Almost tight error bounds on differentially private continual counting. arXiv preprint arXiv:2211.05006 (2022)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_2_1_33_1","volume-title":"International Conference on Machine Learning. PMLR, 5213--5225","author":"Kairouz Peter","year":"2021","unstructured":"Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. 2021. Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning. PMLR, 5213--5225."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342274"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_38_1","volume-title":"SNAP: Stanford network analysis project.","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP: Stanford network analysis project."},{"key":"e_1_2_1_39_1","volume-title":"SNAP datasets: Stanford large network dataset collection","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2016. SNAP datasets: Stanford large network dataset collection (2014). URL http:\/\/snap. stanford. edu\/data (2016), 49."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/646491.694954"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0398-x"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1397735.1397742"},{"key":"e_1_2_1_44_1","volume-title":"USENIX Symposium on Operating Systems Design and Implementation. 149--162","author":"Narayan Arjun","year":"2012","unstructured":"Arjun Narayan and Andreas Haeberlen. 2012. DJoin: Differentially private join queries over distributed databases. In USENIX Symposium on Operating Systems Design and Implementation. 149--162."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Catuscia Palamidessi and Marco Stronati. 2012. Differential Privacy for Relational Algebra: Improving the Sensitivity Bounds via Constraint Systems. In QAPL.","DOI":"10.4204\/EPTCS.85.7"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2019.23535"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732296.2732300"},{"key":"e_1_2_1_49_1","volume-title":"Differential Privacy on Dynamic Data. arXiv preprint arXiv:2209.01387","author":"Qiu Yuan","year":"2022","unstructured":"Yuan Qiu and Ke Yi. 2022. Differential Privacy on Dynamic Data. arXiv preprint arXiv:2209.01387 (2022)."},{"key":"e_1_2_1_50_1","volume-title":"Differentially private continual release of graph statistics. arXiv preprint arXiv:1809.02575","author":"Song Shuang","year":"2018","unstructured":"Shuang Song, Susan Little, Sanjay Mehta, Staal Vinterbo, and Kamalika Chaudhuri. 2018. Differentially private continual release of graph statistics. arXiv preprint arXiv:1809.02575 (2018)."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3632093.3632102"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_2_1_53_1","volume-title":"International Conference on Machine Learning. PMLR, 6363--6372","author":"Upadhyay Jalaj","year":"2019","unstructured":"Jalaj Upadhyay. 2019. Sublinear space private algorithms under the sliding window model. In International Conference on Machine Learning. PMLR, 6363--6372."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579080"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484750"},{"key":"e_1_2_1_56_1","volume-title":"Differentially Private Stream Processing at Scale. arXiv preprint arXiv:2303.18086","author":"Zhang Bing","year":"2023","unstructured":"Bing Zhang, Vadym Doroshenko, Peter Kairouz, Thomas Steinke, Abhradeep Thakurta, Ziyin Ma, Himani Apte, and Jodi Spacek. 2023. Differentially Private Stream Processing at Scale. arXiv preprint arXiv:2303.18086 (2023)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654931","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654931","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654931","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:37:55Z","timestamp":1755787075000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654931"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654931"],"URL":"https:\/\/doi.org\/10.1145\/3654931","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}