English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider the problem of computing differentially private approximatehistograms and heavy hitters in a stream of elements. In the non-privatesetting, this is often done using the sketch of Misra and Gries [Science ofComputer Programming, 1982]. Chan, Li, Shi, and Xu [PETS 2012] describe adifferentially private version of the Misra-Gries sketch, but the amount ofnoise it adds can be large and scales linearly with the size of the sketch; themore accurate the sketch is, the more noise this approach has to add. Wepresent a better mechanism for releasing a Misra-Gries sketch under$(\varepsilon,\delta)$-differential privacy. It adds noise with magnitudeindependent of the size of the sketch; in fact, the maximum error coming fromthe noise is the same as the best known in the private non-streaming setting,up to a constant factor. Our mechanism is simple and likely to be practical. Wealso give a simple post-processing step of the Misra-Gries sketch that does notincrease the worst-case error guarantee. It is sufficient to add noise to thisnew sketch with less than twice the magnitude of the non-streaming setting.This improves on the previous result for $\varepsilon$-differential privacywhere the noise scales linearly to the size of the sketch. Finally, we considera general setting where users can contribute multiple distinct elements. Wepresent a new sketch with maximum error matching the Misra-Gries sketch. Formany parameters in this setting our sketch can be released with less noiseunder $(\varepsilon, \delta)$-differential privacy.

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