{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:36:22Z","timestamp":1755999382292,"version":"3.44.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["2130536, 2342245, 2130608, 342244"],"award-info":[{"award-number":["2130536, 2342245, 2130608, 342244"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ministry of Education Singapore","award":["R-252-000-B59-114, MOE-T2EP20121-0011"],"award-info":[{"award-number":["R-252-000-B59-114, MOE-T2EP20121-0011"]}]},{"DOI":"10.13039\/501100006374","name":"National Research Foundation Singapore","doi-asserted-by":"publisher","award":["NRF-NRFFAI1-2019-0004"],"award-info":[{"award-number":["NRF-NRFFAI1-2019-0004"]}],"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,5,10]]},"abstract":"<jats:p>In today's digital age, it is becoming increasingly prevalent to retain digital footprints in the cloud indefinitely. Nonetheless, there is a valid argument that entities should have the authority to decide whether their personal data remains within a specific database or is expunged. Indeed, nations across the globe are increasingly enacting legislation to uphold the \"Right To Be Forgotten\" for individuals. Investigating computational challenges, including the formalization and implementation of this notion, is crucial due to its relevance in the domains of data privacy and management.<\/jats:p>\n          <jats:p>\n            This work introduces a new streaming model: the 'Right to be Forgotten Data Streaming Model' (RFDS model). The main feature of this model is that any element in the stream has the right to have its history removed from the stream. Formally, the input is a stream of updates of the form (a, \u0394) where \u0394 \u2208 {+, \u22a5} and a is an element from a universe U. When the update \u0394=+ occurs, the frequency of a, denoted as f\n            <jats:sub>a<\/jats:sub>\n            , is incremented to f\n            <jats:sub>a<\/jats:sub>\n            +1. When the update \u0394=\u22a5, occurs, f\n            <jats:sub>a<\/jats:sub>\n            is set to 0. This feature, which represents the forget request, distinguishes the present model from existing data streaming models.\n          <\/jats:p>\n          <jats:p>\n            This work systematically investigates computational challenges that arise while incorporating the notion of the right to be forgotten. Our initial considerations reveal that even estimating F\n            <jats:sub>1<\/jats:sub>\n            (sum of the frequencies of elements) of the stream is a non-trivial problem in this model. Based on the initial investigations, we focus on a modified model which we call \u03b1-RFDS where we limit the number of forget operations to be at most \u03b1 fraction. In this modified model, we focus on estimating F\n            <jats:sub>0<\/jats:sub>\n            (number of distinct elements) and F\n            <jats:sub>1<\/jats:sub>\n            . We present algorithms and establish almost-matching lower bounds on the space complexity for these computational tasks.\n          <\/jats:p>","DOI":"10.1145\/3651603","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-17","source":"Crossref","is-referenced-by-count":1,"title":["On the Feasibility of Forgetting in Data Streams"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1665-5266","authenticated-orcid":false,"given":"A.","family":"Pavan","sequence":"first","affiliation":[{"name":"Iowa State University, Ames, IA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9518-6204","authenticated-orcid":false,"given":"Sourav","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata, WB, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7959-4662","authenticated-orcid":false,"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[{"name":"University of Nebraska-Lincoln, Lincoln, NE, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9423-5270","authenticated-orcid":false,"given":"Kuldeep S","family":"Meel","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2017. Theworld's most valuable resource is no longer oil but data. https:\/\/www.economist.com\/leaders\/2017\/05\/06\/theworlds-most-valuable-resource-is-no-longer-oil-but-data"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_3_1","volume-title":"6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13--15, 2002, Proceedings (Lecture Notes in Computer Science","volume":"10","author":"Bar-Yossef Ziv","year":"2022","unstructured":"Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. 2022. Counting Distinct Elements in a Data Stream. In Randomization and Approximation Techniques, 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13--15, 2002, Proceedings (Lecture Notes in Computer Science, Vol. 2483), Jos\u00e9 D. P. Rolim and Salil P. VadMuth (Eds.). 1--10."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the ninth annual ACM symposium on Theory of computing. ACM, 106--112","author":"Lawrence Carter J","year":"1977","unstructured":"J Lawrence Carter and Mark N Wegman. 1977. Universal classes of hash functions. In Proceedings of the ninth annual ACM symposium on Theory of computing. ACM, 106--112."},{"key":"e_1_2_1_5_1","unstructured":"Amit Chakrabarti. 2023. Data Stream Algorithms Lecture Notes. https:\/\/www.cs.dartmouth.edu\/~ac\/Teach\/datastreams-lecnotes.pdf"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Graham Cormode Minos Garofalakis Peter J Haas Chris Jermaine et al. 2011. Synopses for massive data: Samples histograms wavelets sketches. Foundations and Trends\u00ae in Databases 4 1--3 (2011) 1--294.","DOI":"10.1561\/1900000004"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001","author":"Phillip","year":"2001","unstructured":"Phillip B. Gibbons and Srikanta Tirthapura. 2001. Estimating simple functions on the union of data streams. In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, Heraklion, Crete Island, Greece, July 4--6, 2001, Arnold L. Rosenberg (Ed.). ACM, 281--291."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74450-4_27"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196986"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225277"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1140103.1140295"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458333"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781933019604"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594554"},{"key":"e_1_2_1_17_1","volume-title":"https:\/\/eur-lex.europa.eu\/legal-content\/EN\/TXT\/PDF\/?uri=CELEX:32016R0679 Accessed on","author":"The Europian Parliament and the Council of the Europian Union. 2022. Regulation (EU) 2016\/679 of the European parliament and of the council.","year":"2023","unstructured":"The Europian Parliament and the Council of the Europian Union. 2022. Regulation (EU) 2016\/679 of the European parliament and of the council. https:\/\/eur-lex.europa.eu\/legal-content\/EN\/TXT\/PDF\/?uri=CELEX:32016R0679 Accessed on 19 Sep 2023."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651603","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651603","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:38:57Z","timestamp":1755898737000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651603"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651603"],"URL":"https:\/\/doi.org\/10.1145\/3651603","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}