Abstract
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 finegrained questions about the difference between two data sets. In this work we consider how to construct sketches for weighted F₀, 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 x∘w₁ 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 ℋ. Differential privacy is achieved by using randomized response, flipping each bit of Hx with probability p < 1/2. That is, for a vector φ ∈ {0,1}^τ where Pr[(φ)_j = 1] = p independently for each entry j, we consider the noisy sketch Hx + φ, where the addition of noise happens over GF(2). We show that for every choice of 0 < β < 1 and ε = O(1) there exists p < 1/2 and a distribution ℋ of linear sketches of size τ = O(log²(u)ε^{2}β^{2}) such that:
1) For random H∼ℋ and noise vector φ, given Hx + φ we can compute an estimate of x∘w₁ that is accurate within a factor 1±β, plus additive error O(log(u)ε^{2}β^{2}), w. p. 1u^{1}, and
2) For every H∼ℋ, Hx + φ is εdifferentially private over the randomness in φ. The special case w = (1,… ,1) is unweighted F₀. Previously, Mir et al. (PODS 2011) and Kenthapadi et al. (J. Priv. Confidentiality 2013) had described a differentially private way of sketching unweighted F₀, but the algorithms for calibrating noise to their sketches are not computationally efficient, either using quasipolynomial time in the sketch size or superlinear time in the universe size u.
For fixed ε the size of our sketch is polynomially related to the lower bound of Ω(log(u)β^{2}) bits by Jayram & Woodruff (Trans. Algorithms 2013). The additive error is comparable to the bound of Ω(1/ε) of Hardt & Talwar (STOC 2010). An application of our sketch is that two sketches can be added to form a noisy sketch of the form H(x₁+x₂) + (φ₁+φ₂), which allows us to estimate (x₁+x₂)∘w₁. Since addition is over GF(2), this is the weight of the symmetric difference of the vectors x₁ and x₂. Recent work has shown how to privately and efficiently compute an estimate for the symmetric difference size of two sets using (nonlinear) sketches such as FMsketches and Bloom Filters, but these methods have an error bound no better than O(√{̄{m}}), where ̄{m} is an upper bound on x₁₀ and x₂₀. This improves previous work when β = o (1/√{̄{m}}) and log(u)/ε = ̄{m}^{o(1)}.
In conclusion our results both improve the efficiency of existing methods for unweighted F₀ estimation and extend to a weighted generalization. We also give a distributed streaming implementation for estimating the size of the union between two input streams.
BibTeX  Entry
@InProceedings{pagh_et_al:LIPIcs.ICDT.2021.18,
author = {Pagh, Rasmus and Stausholm, Nina Mesing},
title = {{Efficient Differentially Private F₀ Linear Sketching}},
booktitle = {24th International Conference on Database Theory (ICDT 2021)},
pages = {18:118:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771795},
ISSN = {18688969},
year = {2021},
volume = {186},
editor = {Yi, Ke and Wei, Zhewei},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13726},
URN = {urn:nbn:de:0030drops137264},
doi = {10.4230/LIPIcs.ICDT.2021.18},
annote = {Keywords: Differential Privacy, Linear Sketches, Weighted F0 Estimation}
}
Keywords: 

Differential Privacy, Linear Sketches, Weighted F0 Estimation 
Collection: 

24th International Conference on Database Theory (ICDT 2021) 
Issue Date: 

2021 
Date of publication: 

11.03.2021 