On the Feasibility of Forgetting in Data Streams
Open Access
- 10 May 2024
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (2) , 1-17
Abstract
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. 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, Δ) where Δ ∈ {+, ⊥} and a is an element from a universe U. When the update Δ=+ occurs, the frequency of a, denoted as f a , is incremented to f a +1. When the update Δ=⊥, occurs, f a is set to 0. This feature, which represents the forget request, distinguishes the present model from existing data streaming models. 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 1 (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 α-RFDS where we limit the number of forget operations to be at most α fraction. In this modified model, we focus on estimating F 0 (number of distinct elements) and F 1 . We present algorithms and establish almost-matching lower bounds on the space complexity for these computational tasks.Keywords
Funding Information
- NSF (2130536, 2342245, 2130608, 342244)
- National Research Foundation Singapore (NRF-NRFFAI1-2019-0004)
- Ministry of Education Singapore (R-252-000-B59-114, MOE-T2EP20121-0011)
This publication has 13 references indexed in Scilit:
- Estimating the Size of Union of Sets in Streaming Models2021
- Data Streams with Bounded Deletions2018
- Is min-wise hashing optimal for summarizing set intersection?2014
- Synopses for Massive Data: Samples, Histograms, Wavelets, SketchesFoundations and Trends® in Databases, 2011
- An optimal algorithm for the distinct elements problem2010
- Streaming Algorithms for Data in Motion2007
- Data streaming algorithms for estimating entropy of network trafficACM SIGMETRICS Performance Evaluation Review, 2006
- Stable distributions, pseudorandom generators, embeddings, and data stream computationJournal of the ACM, 2006
- The space complexity of approximating the frequency moments1996
- On randomized one-round communication complexity1995