{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:32:33Z","timestamp":1772119953081,"version":"3.50.1"},"reference-count":3,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:p>This errata article points out an implicit assumption in the work of four of us published in VLDB 2022. The SpaceSaving\u00b1 algorithm in bounded deletion data stream presented in the paper implicitly assumed deletions happen after all insertions. When insertions and deletions are interleaved, that algorithm may severely underestimate item's frequency. We first illustrate this phenomenon by an example and then present a modified algorithm with minor changes to allow interleaving between insertions and deletions. We also include a pointer to a full analysis of the new algorithms.<\/jats:p>","DOI":"10.14778\/3636218.3636221","type":"journal-article","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:04:07Z","timestamp":1709658247000},"page":"643-643","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Errata for \"SpaceSaving\u00b1: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model\""],"prefix":"10.14778","volume":"17","author":[{"given":"Fuheng","family":"Zhao","sequence":"first","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Divyakant","family":"Agrawal","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amr El","family":"Abbadi","sequence":"additional","affiliation":[{"name":"UC Santa Barbara"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ahmed","family":"Metwally","sequence":"additional","affiliation":[{"name":"Uber, Inc."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[{"name":"CNRS and IRIF"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michel","family":"de Rougemont","sequence":"additional","affiliation":[{"name":"University Paris II and IRIF"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,3,5]]},"reference":[{"key":"e_1_2_1_1_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."},{"key":"e_1_2_1_2_1","volume-title":"Claire Mathieu, Ahmed Metwally, and Michel de Rougemont.","author":"Zhao Fuheng","year":"2023","unstructured":"Fuheng Zhao, Divyakant Agrawal, Amr El Abbadi, Claire Mathieu, Ahmed Metwally, and Michel de Rougemont. 2023. A Detailed Analysis of the SpaceSaving\u00b1 Family of Algorithms with Bounded Deletions. arXiv:2309.12623 [cs.DB]"},{"key":"e_1_2_1_3_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 preprint arXiv:2112.03462 (2021)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3636218.3636221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:08:31Z","timestamp":1709658511000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3636218.3636221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12]]},"references-count":3,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10.14778\/3636218.3636221"],"URL":"https:\/\/doi.org\/10.14778\/3636218.3636221","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,12]]},"assertion":[{"value":"2024-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}