2020/01/31 by Pagh, Rasmus, Stausholm, Nina Mesing
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2001.11932
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,1\u we are interested in estimating \Vert x∘ w\Vert1 where ∘ 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,1\u 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