Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory

Summary: HG-LDP jointly optimizes local differential privacy, bounded memory, and Top-k accuracy for streaming heavy hitters. It introduces three LDP randomization schemes for large domains under bounded memory, achieving 2300x memory savings at 41,270 and favorable privacy/accuracy tradeoffs; code released. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h0e95788296183c4b
Venue: SIGMOD
Year: 2024
Pagerank: 5.4764188e-05
Overall Rank: 7,694 | 48.28%
DOI: 10.1145/3639285

Incoming Non-self Citations Over Time

Authors

1. Xiaochen Li (Zhejiang University)
2. Weiran Liu (Alibaba)
3. Jian Lou (Zhejiang University)
4. Yuan Hong (University of Connecticut)
5. Lei Zhang (Alibaba)
6. Zhan Qin (Zhejiang University)
7. Kui Ren (Zhejiang University)

BibTeX Citation

@inproceedings{li_sigmod24,
        title = {{Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory}},
        author = {Li, Xiaochen and Liu, Weiran and Lou, Jian and Hong, Yuan and Zhang, Lei and Qin, Zhan and Ren, Kui},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3639285},
        url = {https://dl.acm.org/doi/10.1145/3639285},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,868	Federated Heavy Hitter Analytics with Local Differential Privacy	2025	SIGMOD	5.9648445e-05
9,477	SPAS: Continuous Release of Data Streams under w-Event Differential Privacy	2025	SIGMOD	5.1708619e-05
10,631	Defense against Poisoning Attacks under Shuffle-DP	2026	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
83	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00035978046
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030600691
226	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.00023984903
858	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.000134266
909	Finding Frequent Items in Data Streams	2008	VLDB	0.00013125647
1,319	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011045888
1,970	Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing	2018	SIGMOD	9.2902522e-05
2,118	Differentially Private Event Sequences over Infinite Streams	2014	VLDB	9.0124362e-05
3,174	CGM: An Enhanced Mechanism for Streaming Data Collection with Local Differential Privacy	2021	VLDB	7.5678238e-05
3,203	Frequency Estimation under Local Differential Privacy	2021	VLDB	7.5406431e-05
3,234	LDP-IDS: Local Differential Privacy for Infinite Data Streams	2022	SIGMOD	7.5031195e-05
3,326	Sliding-Window Top-k Queries on Uncertain Streams	2008	VLDB	7.4227632e-05
3,379	Ad-hoc Top-k Query Answering for Data Streams	2007	VLDB	7.3568458e-05
3,917	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.9266831e-05
5,157	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB	6.2494766e-05
7,637	Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation	2022	VLDB	5.477389e-05
8,162	Diversity-Aware Top-k Publish/Subscribe for Text Stream	2015	SIGMOD	5.3862637e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,873	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD
2	5,673	Mining Frequent Patterns with Differential Privacy	2013	VLDB
3	10,539	A General Framework for Per-record Differential Privacy	2026	SIGMOD
4	7,992	Differentially Private Hierarchical Heavy Hitters	2024	PODS
5	3,203	Frequency Estimation under Local Differential Privacy	2021	VLDB
6	11,183	Efficient and Accurate Differentially Private Cardinality Continual Releases	2025	SIGMOD
7	2,416	On Differentially Private Frequent Itemset Mining	2013	VLDB
8	5,868	Federated Heavy Hitter Analytics with Local Differential Privacy	2025	SIGMOD
9	11,090	Private Synthetic Data Generation in Bounded Memory	2025	PODS
10	3,234	LDP-IDS: Local Differential Privacy for Infinite Data Streams	2022	SIGMOD