• 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 Sun Apr 14, 2024 11:15:51