Pan-private Algorithms Via Statistics on Sketches

Summary: First pan-private algorithms for fully dynamic streaming tasks (distinct counts, frequency moments, heavy hitters) by adapting sketches—calibrating noise to sketch projections, maintaining statistics on sketches, and designing new sketches. Also gives the first pan-privacy lower bounds via a noisy-decoding/sanitization connection, nearly matching the upper bounds and strictly stronger than bounds from differential privacy or streaming alone. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1534
Venue: PODS
Year: 2011
Pagerank: 7.8836024e-05
Overall Rank: 2,992 | 79.48%
DOI: 10.1145/1989284.1989290

Incoming Non-self Citations Over Time

Authors

1. Darakhshan Mir (Rutgers University)
2. S. Muthukrishnan (Rutgers University)
3. Aleksandar Nikolov (Rutgers University)
4. Rebecca N. Wright (Rutgers University)

BibTeX Citation

@inproceedings{mir_pods11,
        address = {New York, NY, USA},
        series = {{PODS} '11},
        title = {{Pan-private Algorithms Via Statistics on Sketches}},
        url = {https://dl.acm.org/doi/10.1145/1989284.1989290},
        doi = {10.1145/1989284.1989290},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Mir, Darakhshan and Muthukrishnan, S. and Nikolov, Aleksandar and Wright, Rebecca N.},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,074	Differentially Private Event Sequences over Infinite Streams	2014	VLDB	9.2192882e-05
3,854	Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch	2023	PODS	7.0723123e-05
6,826	Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy	2025	PODS	5.7621757e-05
10,158	Improved Lower Bounds for Privacy under Continual Release	2026	PODS	5.093636e-05
11,130	Continual Release of Differentially Private Synthetic Data from Longitudinal Data Collections	2024	PODS	5.093636e-05
11,531	The White-Box Adversarial Data Stream Model	2022	PODS	5.093636e-05
11,637	Improved Differentially Private Euclidean Distance Approximation	2021	PODS	5.093636e-05
13,682	Theory of Data Stream Computing: Where to Go	2011	PODS	-

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
123	Revealing Information while Preserving Privacy	2003	PODS	0.00031082693
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
3,150	Comparing Data Streams Using Hamming Norms (How to Zero In)	2002	VLDB	7.7055991e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,164	An LDP Compatible Sketch for Securely Approximating Set Intersection Cardinalities	2024	SIGMOD
2	10,310	A Fast, Mergeable, and LDP Compatible Sketch for Counting the Number of Distinct Values in Fully Dynamic Tables	2026	SIGMOD
3	123	Revealing Information while Preserving Privacy	2003	PODS
4	2,074	Differentially Private Event Sequences over Infinite Streams	2014	VLDB
5	10,335	A General Framework for Per-record Differential Privacy	2026	SIGMOD
6	6,826	Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy	2025	PODS
7	10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD
8	10,647	Private Synthetic Data Generation in Bounded Memory	2025	PODS
9	9,001	Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation	2008	SIGMOD
10	2,862	Privacy via Pseudorandom Sketches	2006	PODS