Post

The first paper co-authored with my student Sia Sejer is out! We show how to do continual observation of sketches (and other data structures) with only a constant-factor time overhead relative to the non-private versions.

The idea is to simulate the distribution of the binary tree mechanism without generating all noise values. Only when accessing a sketch entry do we generate the noise, and with a suitable data structure of size O(log T) it turns out that this is possible in constant time!

The paper also contains a new analysis of the binary tree mechanism with Gaussian noise, which turns out to have a better utility-privacy trade-off than some later refinements such as the smooth binary mechanism.

Finally, we present two applications based on Private CountSketch: An improved range counting data structure, and private sketches for join size (aka. F2) estimation.