On the Feasibility of Forgetting in Data Streams
Proceedings of the ACM on Management of Data · 10.05.2024 · 2 (2) · 1-17
DOI: 10.1145/3651603 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2024. Verfasst von A. Pavan und 3 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 17 Literaturangaben. Gefördert von: NSF, Ministry of Education Singapore, National Research Foundation Singapore.
Abstract (Originalsprache)
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.
Förderung
- NSF
- Ministry of Education Singapore
- National Research Foundation Singapore
Zitieren
APA
Pavan, A., Chakraborty, S., Vinodchandran, N. V., & Meel, K. S. (2024). On the Feasibility of Forgetting in Data Streams. Proceedings of the ACM on Management of Data, 2(2), 1-17. https://doi.org/10.1145/3651603
Vancouver
Pavan A, Chakraborty S, Vinodchandran NV, Meel KS. On the Feasibility of Forgetting in Data Streams. Proceedings of the ACM on Management of Data. 2024;2(2):1-17. doi:10.1145/3651603
BibTeX
@article{Pavan2024,
author = {Pavan, A. and Chakraborty, Sourav and Vinodchandran, N. V. and Meel, Kuldeep S},
title = {On the Feasibility of Forgetting in Data Streams},
journal = {Proceedings of the ACM on Management of Data},
year = {2024},
volume = {2},
number = {2},
pages = {1--17},
doi = {10.1145/3651603}
}
EUVIMED