On the Feasibility of Forgetting in Data Streams

Summary: Introduces the Right-to-be-Forgotten Data Streaming (RFDS) model where updates are + or forget, incrementing or resetting an element’s frequency to zero to capture data-erasure semantics. In alpha-RFDS (forget-bounded by alpha), provides F0 and F1 estimators with almost-tight space lower bounds and practical algorithms. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 1933
Venue: PODS
Year: 2024
Pagerank: 4.427232e-05
Overall Rank: 8,901 | 38.08%
DOI: 10.1145/3651603

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,353	Perfect Sampling in Turnstile Streams Beyond Small Moments	2025	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
383	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00024820873
3,708	Is Min-Wise Hashing Optimal for Summarizing Set Intersection?	2014	PODS	6.8247903e-05
11,442	Estimating the Size of Union of Sets in Streaming Models	2021	PODS	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
10,983	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1945683e-05
4,449	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB	6.1780147e-05
11,833	Streaming Algorithms for Robust Distinct Elements	2016	SIGMOD	4.1945683e-05
6,599	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9973567e-05
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
11,440	Frequent Elements with Witnesses in Data Streams	2021	PODS	4.1945683e-05
10,480	Efficient and Accurate Differentially Private Cardinality Continual Releases	2025	SIGMOD	4.1945683e-05
10,676	Meaningful Data Erasure in the Presence of Dependencies	2025	VLDB	4.1945683e-05
5,433	"Amnesia" - A Selection of Machine Learning Models That Can Forget User Data Very Fast	2020	CIDR	5.5051607e-05
10,116	Stochastic Submodular Data Forgetting	2026	SIGMOD	4.1945683e-05