{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:12:15Z","timestamp":1775913135517,"version":"3.50.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2021YFB1715600"],"award-info":[{"award-number":["2021YFB1715600"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Shenzhen Basic Research Grant","award":["JCYJ20170816100819428"],"award-info":[{"award-number":["JCYJ20170816100819428"]}]},{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U22B2019, 62272372"],"award-info":[{"award-number":["U22B2019, 62272372"]}],"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":[[2024,3,12]]},"abstract":"<jats:p>Given two sets of elements held by two different parties separately, computing the cardinality (i.e., the number of distinct elements) of their intersection set is a fundamental task in applications such as network monitoring and database systems. To handle large sets with limited space, computation, and communication costs, lightweight probabilistic methods (i.e., sketch methods) such as the Flajolet-Martin (FM) sketch and the HyperLogLog (HLL) sketch are extensively used. However, when a set's probabilistic data summary and the hash functions used to construct the sketch are disclosed to an untrusted third party, the set's privacy is compromised. Directly applyingLocal Differential Privacy (LDP) techniques to safeguard the sketch collection results in extremely large estimation errors of set intersection cardinalities. To address this issue, we propose a novel sketch method that makes it easier to incorporate noise into the constructed sketch to achieve differential privacy. More importantly, our sketch method is compatible with the LDP noise. In other words, the probabilistic model underlying our LDP-based data summary is quite basic, allowing us to eliminate the estimation error generated by the noise. We perform extensive experiments on various synthetic and real-world datasets and the experimental results demonstrate that our method is orders of magnitude more accurate and several times faster than state-of-the-art methods.<\/jats:p>","DOI":"10.1145\/3639281","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-27","source":"Crossref","is-referenced-by-count":6,"title":["An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1434-837X","authenticated-orcid":false,"given":"Pinghui","family":"Wang","sequence":"first","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University &amp; Shenzhen Research Institute of Xi'an Jiaotong University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-1779-7830","authenticated-orcid":false,"given":"Yitong","family":"Liu","sequence":"additional","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-0857-4573","authenticated-orcid":false,"given":"Zhicheng","family":"Li","sequence":"additional","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0354-9536","authenticated-orcid":false,"given":"Rundong","family":"Li","sequence":"additional","affiliation":[{"name":"MOE KLINNS Lab, Xi'an Jiaotong University, Xi'an, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_1"},{"key":"e_1_2_1_2_1","volume-title":"Probability and Measure","author":"Billingsley Patrick","unstructured":"Patrick Billingsley. 1986. Probability and Measure second ed.). John Wiley and Sons."},{"key":"e_1_2_1_3_1","volume-title":"Network applications of bloom filters: A survey. Internet mathematics","author":"Broder Andrei","year":"2004","unstructured":"Andrei Broder and Michael Mitzenmacher. 2004. Network applications of bloom filters: A survey. Internet mathematics, Vol. 1, 4 (2004), 485--509."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3097999"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3197390"},{"key":"e_1_2_1_6_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Dahlgaard S\u00f8ren","year":"2017","unstructured":"S\u00f8ren Dahlgaard, Mathias Knudsen, and Mikkel Thorup. 2017. Practical hash functions for similarity estimation and dimensionality reduction. Advances in Neural Information Processing Systems, Vol. 30 (2017)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564719"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10207-012-0183-4"},{"key":"e_1_2_1_9_1","volume-title":"PIR-PSI: scaling private contact discovery. Cryptology ePrint Archive","author":"Demmler Daniel","year":"2018","unstructured":"Daniel Demmler, Peter Rindal, Mike Rosulek, and Ni Trieu. 2018. PIR-PSI: scaling private contact discovery. Cryptology ePrint Archive (2018)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2019-0018"},{"key":"e_1_2_1_11_1","first-page":"15204","article-title":"Order-invariant cardinality estimators are differentially private","volume":"35","author":"Dickens Charlie","year":"2022","unstructured":"Charlie Dickens, Justin Thaler, and Daniel Ting. 2022. Order-invariant cardinality estimators are differentially private. Advances in Neural Information Processing Systems, Vol. 35 (2022), 15204--15216.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_12_1","volume-title":"Advances in Neural Information Processing Systems","volume":"30","author":"Ding Bolin","year":"2017","unstructured":"Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately. Advances in Neural Information Processing Systems, Vol. 30 (2017)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516701"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings 11","author":"Durand Marianne","year":"2003","unstructured":"Marianne Durand and Philippe Flajolet. 2003. Loglog counting of large cardinalities. In Algorithms-ESA 2003: 11th Annual European Symposium, Budapest, Hungary, September 16--19, 2003. Proceedings 11. Springer, 605--617."},{"key":"e_1_2_1_16_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_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Philippe Flajolet \u00c9ric Fusy Olivier Gandouet and Fr\u00e9d\u00e9ric Meunier. 2007. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In Discrete Mathematics and Theoretical Computer Science. Discrete Mathematics and Theoretical Computer Science 137--156.","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-014-9190-0"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"e_1_2_1_22_1","volume-title":"CRYPTO 2021, Virtual Event, August 16--20, 2021, Proceedings, Part II 41","author":"Garimella Gayathri","year":"2021","unstructured":"Gayathri Garimella, Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. 2021. Oblivious key-value stores and amplification for private set intersection. In Advances in Cryptology--CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16--20, 2021, Proceedings, Part II 41. Springer, 395--425."},{"key":"e_1_2_1_23_1","volume-title":"Secure multi-party computation. Manuscript. Preliminary version","author":"Goldreich Oded","year":"1998","unstructured":"Oded Goldreich. 1998. Secure multi-party computation. Manuscript. Preliminary version, Vol. 78, 110 (1998)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3546191"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"J. Hartung G. Knapp and B.K. Sinha. 2008. Statistical Meta-Analysis with Applications. Wiley.","DOI":"10.1002\/9780470386347"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"12865","author":"Hehir Jonathan","year":"2023","unstructured":"Jonathan Hehir, Daniel Ting, and Graham Cormode. 2023. Sketch-Flip-Merge: Mergeable Sketches for Private Distinct Counting. In Proceedings of the 40th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 202), Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (Eds.). PMLR, 12846--12865. https:\/\/proceedings.mlr.press\/v202\/hehir23a.html"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452456"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1080\/00031305.2012.687494"},{"key":"e_1_2_1_29_1","unstructured":"Yan Huang David Evans and Jonathan Katz. 2012. Private set intersection: Are garbled circuits better than custom protocols?. In NDSS."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611508"},{"key":"e_1_2_1_31_1","volume-title":"2023 b. The Fast and the Private: Task-based Dataset Search. arXiv preprint arXiv:2308.05637","author":"Huang Zezhou","year":"2023","unstructured":"Zezhou Huang, Jiaxiang Liu, Haonan Wang, and Eugene Wu. 2023 b. The Fast and the Private: Task-based Dataset Search. arXiv preprint arXiv:2308.05637 (2023)."},{"key":"e_1_2_1_32_1","volume-title":"28th USENIX Security Symposium (USENIX Security 19)","author":"Kales Daniel","year":"2019","unstructured":"Daniel Kales, Christian Rechberger, Thomas Schneider, Matthias Senker, and Christian Weinert. 2019. Mobile private contact discovery at scale. In 28th USENIX Security Symposium (USENIX Security 19). 1447--1464."},{"key":"e_1_2_1_33_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978381"},{"key":"e_1_2_1_35_1","volume-title":"Evgeny Sergeevich Skvortsov, Raimundo Mirisola, and Yao Wang.","author":"Kreuter Benjamin","year":"2020","unstructured":"Benjamin Kreuter, Craig William Wright, Evgeny Sergeevich Skvortsov, Raimundo Mirisola, and Yao Wang. 2020. Privacy-Preserving Secure Cardinality and Frequency Estimation. Technical Report. Google, LLC."},{"key":"e_1_2_1_36_1","volume-title":"2012 Proceedings IEEE INFOCOM. IEEE, 2526--2530","author":"Li Tao","year":"2012","unstructured":"Tao Li, Shigang Chen, and Yan Qiao. 2012. Origin-destination flow measurement in high-speed networks. In 2012 Proceedings IEEE INFOCOM. IEEE, 2526--2530."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.1986.10022"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/964725.633041"},{"key":"e_1_2_1_39_1","volume-title":"Efficient Differentially Private $ F_0 $ Linear Sketching. arXiv preprint arXiv:2001.11932","author":"Pagh Rasmus","year":"2020","unstructured":"Rasmus Pagh and Nina Mesing Stausholm. 2020. Efficient Differentially Private $ F_0 $ Linear Sketching. arXiv preprint arXiv:2001.11932 (2020)."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26954-8_13"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45724-2_25"},{"key":"e_1_2_1_42_1","volume-title":"24th USENIX Security Symposium (USENIX Security 15)","author":"Pinkas Benny","year":"2015","unstructured":"Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. 2015. Phasing: Private set intersection using permutation-based hashing. In 24th USENIX Security Symposium (USENIX Security 15). 515--530."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17659-4_5"},{"key":"e_1_2_1_44_1","volume-title":"23rd USENIX Security Symposium (USENIX Security 14)","author":"Pinkas Benny","year":"2014","unstructured":"Benny Pinkas, Thomas Schneider, and Michael Zohner. 2014. Faster private set intersection based on $$OT$$ extension. In 23rd USENIX Security Symposium (USENIX Security 14). 797--812."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3154794"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2969423"},{"key":"e_1_2_1_47_1","volume-title":"25th USENIX Security Symposium (USENIX Security 16)","author":"Rindal Peter","year":"2016","unstructured":"Peter Rindal and Mike Rosulek. 2016. Faster malicious 2-party secure computation with $$Online\/Offline$$ dual execution. In 25th USENIX Security Symposium (USENIX Security 16). 297--314."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77886-6_31"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1254882.1254895"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948237"},{"key":"e_1_2_1_51_1","first-page":"19561","article-title":"The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space","volume":"33","author":"Smith Adam","year":"2020","unstructured":"Adam Smith, Shuang Song, and Abhradeep Guha Thakurta. 2020. The flajolet-martin sketch itself preserves differential privacy: Private counting with minimal space. Advances in Neural Information Processing Systems, Vol. 33 (2020), 19561--19572.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/PAC.2017.43"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2019.2916349"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2021.3120232"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICMCS.2018.8525881"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939772"},{"key":"e_1_2_1_57_1","volume-title":"An Effective and Differentially Private Protocol for Secure Distributed Cardinality Estimation. arXiv preprint arXiv:2302.02158","author":"Wang Pinghui","year":"2023","unstructured":"Pinghui Wang, Chengjin Yang, Dongdong Xie, Junzhou Zhao, Hui Li, Jing Tao, and Xiaohong Guan. 2023. An Effective and Differentially Private Protocol for Secure Distributed Cardinality Estimation. arXiv preprint arXiv:2302.02158 (2023)."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/78922.78925"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.2970860"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2019.2894729"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVT.2015.2436395"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639281","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:15:45Z","timestamp":1755789345000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639281"],"URL":"https:\/\/doi.org\/10.1145\/3639281","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}