• Classified by Research Topic • Sorted by Date • Classified by Publication Type •
On the Feasibility of Forgetting in Data Streams.
A. Pavan, Sourav, Chakraborty, N. V. Vinodchandran and Kuldeep S. Meel.
In Proceedings of ACM Symposium on Principles of Database Systems (PODS), June 2024.
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' (RDFS). 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 $\Fone$ (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 $\alpha$-RFDS where we limit the number of forget operations to be at most $\alpha$ fraction. In this modified model, we focus on estimating F0 (number of distinct elements) and F1. We present algorithms and establish almost-matching lower bounds on the space complexity for these computational tasks.
@inproceedings{pcvm24,
title={On the Feasibility of Forgetting in Data Streams},
author={
Pavan, A. and Chakraborty, Sourav, and Vinodchandran, N. V. and Meel,
Kuldeep S.
},
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' (RDFS).
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 $\Fone$ (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 $\alpha$-RFDS where we limit the number of forget operations
to be at most $\alpha$ fraction.
In this modified model, we focus on estimating F0 (number of distinct
elements) and F1. We present algorithms and establish almost-matching lower
bounds on the space complexity for these computational tasks.
},
month=jun,
year={2024},
booktitle=PODS,
bib2html_pubtype={Refereed Conference},
bib2html_rescat={Data Streams},
bib2html_dl_pdf={../Papers/pods24-pcvm.pdf},
}
Generated by bib2html.pl (written by Patrick Riley with layout from Sanjit A. Seshia ) on Tue Apr 28, 2026 01:27:21