{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:08:07Z","timestamp":1779131287881,"version":"3.51.4"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"HKRGC","award":["16205422"],"award-info":[{"award-number":["16205422"]}]},{"name":"HKRGC","award":["16204223"],"award-info":[{"award-number":["16204223"]}]},{"name":"HKRGC","award":["16203924"],"award-info":[{"award-number":["16203924"]}]},{"name":"HKUST-Alibaba Joint Laboratory on Big Data and Artificial Intelligence","award":["N.A."],"award-info":[{"award-number":["N.A."]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    Sketching is an effective approach to dealing with high-volume streaming plaintext data with bounded memory and computing cost, while providing provable guarantees on the query accuracy. In this paper, we present a sketching framework under the model of outsourced secure multi-party computation (MPC), where data is uploaded to the computing parties in a secret-shared form. We show how our framework supports a variety of sketches, including the Count-Min Sketch, HyperLogLog, SpaceSaving, and the Greenwald-Khanna Sketch, which allow the secure evaluation of group-by aggregation queries, frequency estimation, top-\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    queries, distinct count, and rank\/quantile queries. Our framework can maintain these sketches with\n                    <jats:italic toggle=\"yes\">\u00d5<\/jats:italic>\n                    (1) cost per update amortized, while using a bounded amount of memory that can be configured based on the user's budget and query accuracy requirements. Experimental results show that our framework can process each stream update with an amortized cost of less than 1 ms, significantly outperforming prior work.\n                  <\/jats:p>","DOI":"10.1145\/3802110","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Sketch-based Secure Query Processing for Streaming Data"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-1418-1728","authenticated-orcid":false,"given":"Jianzhe","family":"Yu","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-0696-3008","authenticated-orcid":false,"given":"Feng","family":"Han","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hang Zhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-0498-499X","authenticated-orcid":false,"given":"Qi","family":"Dong","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1466-7418","authenticated-orcid":false,"given":"Weiran","family":"Liu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Bei Jing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-2028-0780","authenticated-orcid":false,"given":"Lin","family":"Qu","sequence":"additional","affiliation":[{"name":"Alibaba Group, Hang Zhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Netflix Prize dataset. https:\/\/archive.org\/download\/nf_prize_dataset.tar. Accessed: 2016-02-04."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2500128"},{"key":"e_1_2_1_3_1","unstructured":"Daniel Alabi Omri Ben-Eliezer and Anamay Chaturvedi. 2022. Bounded Space Differentially Private Quantiles. arXiv:2201.03380 https:\/\/arxiv.org\/abs\/2201.03380"},{"key":"e_1_2_1_4_1","volume-title":"Advances in Cryptology - EUROCRYPT","author":"Albrecht Martin R.","year":"2015","unstructured":"Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. 2015. Ciphers for MPC and FHE. In Advances in Cryptology - EUROCRYPT 2015, Elisabeth Oswald and Marc Fischlin (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 430-454."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484560"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560691"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3576915.3623119"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560670"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jisa.2022.103403"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1468075.1468121"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055334"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291274"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407854"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3731569.3764833"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484557"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654921"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP46215.2023.10179466"},{"key":"e_1_2_1_21_1","volume-title":"Algorithms - ESA","author":"Durand Marianne","year":"2003","unstructured":"Marianne Durand and Philippe Flajolet. 2003. Loglog Counting of Large Cardinalities. In Algorithms - ESA 2003, Giuseppe Di Battista and Uri Zwick (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 605-617."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"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.1561\/3300000019"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658644.3690257"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382251"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375670"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651610"},{"key":"e_1_2_1_30_1","volume-title":"Information Security and Cryptology - ICISC","author":"Hamada Koki","year":"2012","unstructured":"Koki Hamada, Ryo Kikuchi, Dai Ikarashi, Koji Chida, and Katsumi Takahashi. 2013. Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms. In Information Security and Cryptology - ICISC 2012, Taekyoung Kwon, Mun-Kyu Lee, and Daesung Kwon (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 202-216."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00176"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2003.1292373"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 40th International Conference on Machine Learning","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 (Honolulu, Hawaii, USA) (ICML'23). JMLR.org, Article 522, 20 pages."},{"key":"e_1_2_1_34_1","first-page":"965","volume-title":"30th USENIX Security Symposium (USENIX Security 21)","author":"Hu Changhui","year":"2021","unstructured":"Changhui Hu, Jin Li, Zheli Liu, Xiaojie Guo, Yu Wei, Xuan Guang, Grigorios Loukides, and Changyu Dong. 2021. How to Make Private Distributed Cardinality Estimation Practical, and Get Differential Privacy for Free. In 30th USENIX Security Symposium (USENIX Security 21). USENIX Association, 965-982. https:\/\/www.usenix.org\/conference\/usenixsecurity21\/presentation\/hu-changhui"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547312"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2016) (proceedings of the acm sigmod international conference on management of data (sigmod 2016)","author":"Kandula Srikanth","year":"2016","unstructured":"Srikanth Kandula, Anil Shanbhag, Aleksandar Vitorovic, Matthaios Olma, Robert Grandl, Surajit Chaudhuri, and Bolin Ding. 2016. Quickr: Lazily Approximating Complex Ad-Hoc Queries in Big Data Clusters. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD 2016) (proceedings of the acm sigmod international conference on management of data (sigmod 2016) ed.). ACM - Association for Computing Machinery. https:\/\/www.microsoft.com\/en-us\/research\/publication\/quickr-lazily-approximating-complex-ad-hocqueries-in-big-data-clusters\/"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1283920.1283929"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2021.24330"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2023.3272775"},{"key":"e_1_2_1_41_1","first-page":"1031","volume-title":"20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23)","author":"Liagouris John","year":"2023","unstructured":"John Liagouris, Vasiliki Kalavri, Muhammad Faisal, and Mayank Varia. 2023. SECRECY: Secure collaborative analytics in untrusted clouds. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). USENIX Association, Boston, MA, 1031-1056. https:\/\/www.usenix.org\/conference\/nsdi23\/presentation\/liagouris"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617339"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1166074.1166084"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(82)90012-0"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243734.3243760"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3423358"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference (Renton, WA, USA) (USENIX ATC '19). USENIX Association, USA, 537-554","author":"Park Heejin","year":"2019","unstructured":"Heejin Park, Shuang Zhai, Long Lu, and Felix Xiaozhu Lin. 2019. Streambox-TZ: secure stream analytics at the edge with trustzone. In Proceedings of the 2019 USENIX Conference on Usenix Annual Technical Conference (Renton, WA, USA) (USENIX ATC '19). USENIX Association, USA, 537-554."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196905"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146847.1146848"},{"key":"e_1_2_1_50_1","volume-title":"Raluca Ada Popa, and Joseph M. Hellerstein","author":"Poddar Rishabh","year":"2021","unstructured":"Rishabh Poddar, Sukrit Kalra, Avishay Yanai, Ryan Deng, Raluca Ada Popa, and Joseph M. Hellerstein. 2021. Senate: A Maliciously-Secure MPC Platform for Collaborative Analytics. In 30th USENIX Security Symposium (USENIX Security . USENIX Association, 2129-2146. https:\/\/www.usenix.org\/conference\/usenixsecurity21\/presentation\/poddar"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457306"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526151"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588914"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654971"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2810103.2813634"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452808"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524142"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594529"},{"key":"e_1_2_1_60_1","volume-title":"Proceedings of the 36th International Conference on Neural Information Processing Systems","author":"Zhao Fuheng","year":"2022","unstructured":"Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-XiangWang. 2022. Differentially private linear sketches: efficient implementations and applications. In Proceedings of the 36th International Conference on Neural Information Processing Systems (New Orleans, LA, USA) (NIPS '22). Curran Associates Inc., Red Hook, NY, USA, Article 922, 14 pages."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3658644.3690314"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802110","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:36:30Z","timestamp":1779129390000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802110"],"URL":"https:\/\/doi.org\/10.1145\/3802110","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}