Efficient Differentially Private F0 Linear Sketching

A powerful feature of linear sketches is that from sketches of two data vectors, one can compute the sketch of the difference between the vectors. This allows us to answer fine-grained questions about the difference between two data sets. In this work, we consider how to construct sketches for weighted F0, i.e., the summed weights of the elements in the data set, that are small, differentially private, and computationally efficient. Let a weight vector w∈(0,1]u be given. For x∈0,1u we are interested in estimating Vert xcirc wVert1 where circ is the Hadamard product (entrywise product). Building on a technique of Kushilevitz et al.~(STOC 1998), we introduce a sketch (depending on w) that is linear over GF(2), mapping a vector x∈ 0,1u to Hx∈0,1τ for a matrix H sampled from a suitable distribution H. Differential privacy is achieved by using randomized response, flipping each bit of Hx with probability p<1/2. We show that for every choice of 0<β < 1 and varepsilon=O(1) there exists p<1/2 and a distribution H of linear sketches of size τ = O(log2(u)varepsilon-2β-2) such that: 1) For random H~H and noise vector varphi, given Hx + varphi we can compute an estimate of Vert xcirc wVert1 that is accurate within a factor 1±β, plus additive error O(log(u)varepsilon-2β-2), with probability 1-1/u, and 2) For every H~H, Hx + varphi is varepsilon-differentially private over the randomness in varphi. The special case w=(1,dots,1) is unweighted F0. Our results both improve the efficiency of existing methods for unweighted F0 estimating and extend to a weighted generalization. We also give a distributed streaming implementation for estimating the size of the union between two input streams.