Better Differentially Private Approximate Histograms and Heavy Hitters using the Misra-Gries Sketch

Finding repeated elements

J. Misra and D. Gries · 1982

Earlier work this paper cites.

Bounds for frequency estimation of packet streams

P. Bose, E. Kranakis, P. Morin, and Y. Tang · 2003

Earlier work this paper cites.

Calibrating noise to sensitivity in private data analysis

C. Dwork, F. McSherry, K. Nissim, and A. Smith · 2006

Earlier work this paper cites.

Releasing search queries and clicks privately

A. Korolova, K. Kenthapadi, N. Mishra, and A. Ntoulas · 2009

Earlier work this paper cites.

Pan-private algorithms via statistics on sketches

D. J. Mir, S. Muthukrishnan, A. Nikolov, and R. N. Wright · 2011

Earlier work this paper cites.

Differentially private continual monitoring of heavy hitters from distributed streams

T.-H. H. Chan, M. Li, E. Shi, and W. Xu · 2012

Earlier work this paper cites.

Differentially private summaries for sparse data

G. Cormode, C. M. Procopiuc, D. Srivastava, and T. T. L. Tran · 2012

Earlier work this paper cites.

Universally utility-maximizing privacy mechanisms

A. Ghosh, T. Roughgarden, and M. Sundararajan · 2012

Earlier work this paper cites.

Mergeable summaries

P. K. Agarwal, G. Cormode, Z. Huang, J. M. Phillips, Z. Wei, and K. Yi · 2013

Earlier work this paper cites.

The algorithmic foundations of differential privacy

C. Dwork and A. Roth · 2014

Earlier work this paper cites.

Rappor: Randomized aggregatable privacy-preserving ordinal response

Ú. Erlingsson, V. Pihur, and A. Korolova · 2014

Earlier work this paper cites.

The staircase mechanism in differential privacy

Q. Geng, P. Kairouz, S. Oh, and P. Viswanath · 2015

Earlier work this paper cites.

Heavy hitter estimation over set-valued data with local differential privacy

Z. Qin, Y. Yang, T. Yu, I. Khalil, X. Xiao, and K. Ren · 2016

Cited alongside, same era.

Practical locally private heavy hitters

R. Bassily, K. Nissim, U. Stemmer, and A. Guha Thakurta · 2017

Cited alongside, same era.

Differential privacy on finite computers

V. Balcer and S. Vadhan · 2019

Cited alongside, same era.

Heavy hitters and the structure of local privacy

M. Bun, J. Nelson, and U. Stemmer · 2019

Cited alongside, same era.

Practical differentially private top-k selection with pay-what-you-get composition

D. Durfee and R. M. Rogers · 2019

Cited alongside, same era.

On the power of multiple anonymous messages

B. Ghazi, N. Golowich, R. Kumar, R. Pagh, and A. Velingker · 2019

Cited alongside, same era.

Representing sparse vectors with differential privacy, low error, optimal space, and fast access

M. Aumüller, C. J. Lebeda, and R. Pagh · 2022

Later among the works it cites.

How to make your approximation algorithm private: A black-box differentially-private transformation for tunable approximation algorithms of functions with low sensitivity

Original

J. Blocki, E. Grigorescu, T. Mukherjee, and S. Zhou · 2022

Later among the works it cites.

Precision-based attacks and interval refining: how to break, then fix, differential privacy on finite computers

Original

S. Haney, D. Desfontaines, L. Hartman, R. Shrestha, and M. Hay · 2022

Later among the works it cites.

Improved utility analysis of private countsketch

R. Pagh and M. Thorup · 2022

Later among the works it cites.

Asymptotically optimal locally private heavy hitters via parameterized sketches

H. Wu and A. Wirth · 2022

Later among the works it cites.