{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T01:09:42Z","timestamp":1788570582159,"version":"build-2803163510"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:p>\n            In this paper, we propose the first deterministic algorithms to solve the frequency estimation and frequent item problems in the\n            <jats:italic>bounded-deletion<\/jats:italic>\n            model. We establish the space lower bound for solving the deterministic frequent items problem in the bounded-deletion model, and propose Lazy SpaceSaving\n            <jats:sup>\u00b1<\/jats:sup>\n            and SpaceSaving\n            <jats:sup>\u00b1<\/jats:sup>\n            algorithms with optimal space bound. We develop an efficient implementation of the SpaceSaving\n            <jats:sup>\u00b1<\/jats:sup>\n            algorithm that minimizes the latency of update operations using novel data structures. The experimental evaluations testify that SpaceSaving\n            <jats:sup>\u00b1<\/jats:sup>\n            has accurate frequency estimations and achieves very high recall and precision across different data distributions while using minimal space. Our experiments clearly demonstrate that, if allowed the same space, SpaceSaving\u00b1 is more accurate than the state-of-the-art protocols with up to\n            <jats:italic>logU<\/jats:italic>\n            - 1\/\n            <jats:italic>logU<\/jats:italic>\n            of the items deleted, where\n            <jats:italic>U<\/jats:italic>\n            is the size of the input universe. Moreover, motivated by prior work, we propose Dyadic SpaceSaving\n            <jats:sup>\u00b1<\/jats:sup>\n            , the first deterministic quantile approximation sketch in the bounded-deletion model.\n          <\/jats:p>","DOI":"10.14778\/3514061.3514068","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:26:10Z","timestamp":1655936770000},"page":"1215-1227","source":"Crossref","is-referenced-by-count":8,"title":["SpaceSaving\n            <sup>\u00b1<\/sup>"],"prefix":"10.14778","volume":"15","author":[{"given":"Fuheng","family":"Zhao","sequence":"first","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Divyakant","family":"Agrawal","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amr El","family":"Abbadi","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ahmed","family":"Metwally","sequence":"additional","affiliation":[{"name":"Uber, Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Anonymized Internet Traces","year":"2015","unstructured":"[n.d.]. Anonymized Internet Traces 2015 . https:\/\/catalog.caida.org\/details\/dataset\/passive_2015_pcap. Accessed: 2021-11-5. [n.d.]. Anonymized Internet Traces 2015. https:\/\/catalog.caida.org\/details\/dataset\/passive_2015_pcap. Accessed: 2021-11-5."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213562"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2020.2982739"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1862919.1862923"},{"key":"e_1_2_1_7_1","first-page":"1","article-title":"An optimal algorithm for 1-heavy hitters in insertion streams and related problems","volume":"15","author":"Bhattacharyya Arnab","year":"2018","unstructured":"Arnab Bhattacharyya , Palash Dey , and David P Woodruff . 2018 . An optimal algorithm for 1-heavy hitters in insertion streams and related problems . ACM Transactions on Algorithms (TALG) 15 , 1 (2018), 1 -- 27 . Arnab Bhattacharyya, Palash Dey, and David P Woodruff. 2018. An optimal algorithm for 1-heavy hitters in insertion streams and related problems. ACM Transactions on Algorithms (TALG) 15, 1 (2018), 1--27.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_9_1","volume-title":"Automated Reasoning","author":"Boyer Robert S","unstructured":"Robert S Boyer and J Strother Moore . 1991. MJRTY---a fast majority vote algorithm . In Automated Reasoning . Springer , 105--117. Robert S Boyer and J Strother Moore. 1991. MJRTY---a fast majority vote algorithm. In Automated Reasoning. Springer, 105--117."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00038"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034798"},{"key":"e_1_2_1_12_1","volume-title":"International Colloquium on Automata, Languages, and Programming","author":"Charikar Moses","unstructured":"Moses Charikar , Kevin Chen , and Martin Farach-Colton . 2002. Finding frequent items in data streams . In International Colloquium on Automata, Languages, and Programming . Springer , 693--703. Moses Charikar, Kevin Chen, and Martin Farach-Colton. 2002. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming. Springer, 693--703."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454225"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007575"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339496"},{"key":"e_1_2_1_16_1","volume-title":"Frequency Estimation under Local Differential Privacy [Experiments, Analysis and Benchmarks]. arXiv preprint arXiv:2103.16640","author":"Cormode Graham","year":"2021","unstructured":"Graham Cormode , Samuel Maddock , and Carsten Maple . 2021. Frequency Estimation under Local Differential Privacy [Experiments, Analysis and Benchmarks]. arXiv preprint arXiv:2103.16640 ( 2021 ). Graham Cormode, Samuel Maddock, and Carsten Maple. 2021. Frequency Estimation under Local Differential Privacy [Experiments, Analysis and Benchmarks]. arXiv preprint arXiv:2103.16640 (2021)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1061318.1061325"},{"key":"e_1_2_1_19_1","volume-title":"Small Summaries for Big Data","author":"Cormode Graham","unstructured":"Graham Cormode and Ke Yi. 2020. Small Summaries for Big Data . Cambridge University Press . Graham Cormode and Ke Yi. 2020. Small Summaries for Big Data. Cambridge University Press."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.231"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/647912.740658"},{"key":"e_1_2_1_22_1","volume-title":"Internaational Conference on Very Large Databases (VLDB'98)","author":"Fang Min","year":"1999","unstructured":"Min Fang , Narayanan Shivakumar , Hector Garcia-Molina , Rajeev Motwani , and Jeffrey D Ullman . 1999 . Computing Iceberg Queries Efficiently .. In Internaational Conference on Very Large Databases (VLDB'98) , New York , August 1998. Stanford InfoLab. Min Fang, Narayanan Shivakumar, Hector Garcia-Molina, Rajeev Motwani, and Jeffrey D Ullman. 1999. Computing Iceberg Queries Efficiently.. In Internaational Conference on Very Large Databases (VLDB'98), New York, August 1998. Stanford InfoLab."},{"key":"e_1_2_1_23_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.  Philippe Flajolet \u00c9ric Fusy Olivier Gandouet and Fr\u00e9d\u00e9ric Meunier. 2007. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm.","DOI":"10.46298\/dmtcs.3545"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50047-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375670"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956815"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3405669.3405820"},{"key":"e_1_2_1_28_1","volume-title":"Streaming Quantiles Algorithms with Small Space and Update Time. arXiv preprint arXiv:1907.00236","author":"Ivkin Nikita","year":"2019","unstructured":"Nikita Ivkin , Edo Liberty , Kevin Lang , Zohar Karnin , and Vladimir Braverman . 2019. Streaming Quantiles Algorithms with Small Space and Update Time. arXiv preprint arXiv:1907.00236 ( 2019 ). Nikita Ivkin, Edo Liberty, Kevin Lang, Zohar Karnin, and Vladimir Braverman. 2019. Streaming Quantiles Algorithms with Small Space and Update Time. arXiv preprint arXiv:1907.00236 (2019)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196986"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956918"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989289"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384278"},{"key":"e_1_2_1_33_1","volume-title":"Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs)","author":"Karnin Zohar","unstructured":"Zohar Karnin , Kevin Lang , and Edo Liberty . 2016. Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs) . IEEE , 71--78. Zohar Karnin, Kevin Lang, and Edo Liberty. 2016. Optimal quantile approximation in streams. In 2016 ieee 57th annual symposium on foundations of computer science (focs). IEEE, 71--78."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2008.11.001"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50038-X"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/276305.276342"},{"key":"e_1_2_1_38_1","volume-title":"International conference on database theory. Springer, 398--412","author":"Metwally Ahmed","year":"2005","unstructured":"Ahmed Metwally , Divyakant Agrawal , and Amr El Abbadi . 2005 . Efficient computation of frequent and top-k elements in data streams . In International conference on database theory. Springer, 398--412 . Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. 2005. Efficient computation of frequent and top-k elements in data streams. In International conference on database theory. Springer, 398--412."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/867576"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1155\/2005\/962135"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031495.1031524"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3050220.3063772"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183759"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465312"},{"key":"e_1_2_1_45_1","volume-title":"CoT: Decentralized elastic caches for cloud environments. arXiv preprint arXiv:2006.08067","author":"Zakhary Victor","year":"2020","unstructured":"Victor Zakhary , Lawrence Lim , Divyakant Agrawal , and Amr El Abbadi . 2020. CoT: Decentralized elastic caches for cloud environments. arXiv preprint arXiv:2006.08067 ( 2020 ). Victor Zakhary, Lawrence Lim, Divyakant Agrawal, and Amr El Abbadi. 2020. CoT: Decentralized elastic caches for cloud environments. arXiv preprint arXiv:2006.08067 (2020)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452296.3472892"},{"key":"e_1_2_1_47_1","volume-title":"Amr El Abbadi, and Ahmed Metwally","author":"Zhao Fuheng","year":"2021","unstructured":"Fuheng Zhao , Divyakant Agrawal , Amr El Abbadi, and Ahmed Metwally . 2021 . SpaceSaving\u00b1: An Optimal Algorithm for Frequency Estimation and Frequent items in the Bounded Deletion Model . arXiv:2112.03462 [cs.DB] Fuheng Zhao, Divyakant Agrawal, Amr El Abbadi, and Ahmed Metwally. 2021. SpaceSaving\u00b1: An Optimal Algorithm for Frequency Estimation and Frequent items in the Bounded Deletion Model. arXiv:2112.03462 [cs.DB]"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450990"},{"key":"e_1_2_1_49_1","volume-title":"Human behavior and the principle of least effort: An introduction to human ecology","author":"Zipf George Kingsley","unstructured":"George Kingsley Zipf . 2016. Human behavior and the principle of least effort: An introduction to human ecology . Ravenio Books . George Kingsley Zipf. 2016. Human behavior and the principle of least effort: An introduction to human ecology. Ravenio Books."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3514061.3514068","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:24:16Z","timestamp":1672219456000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3514061.3514068"}},"subtitle":["an optimal algorithm for frequency estimation and frequent items in the bounded-deletion model"],"short-title":[],"issued":{"date-parts":[[2022,2]]},"references-count":49,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10.14778\/3514061.3514068"],"URL":"https:\/\/doi.org\/10.14778\/3514061.3514068","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,2]]}}}