Linear Counting Queries under Differential Privacy: A Comparative Study

Abstract

Linear counting queries are found in various data publishing schemes such as OLAPover data cubes, spatial summarization. Under differential privacy, we have thetrade-off between the privacy for contributing individuals and the accuracy of theoutput. To exploit the correlation among linear queries in the batch, some matrixbasedand convex geometry-based methods are proposed along with lower/upperbounds articulated for popular workloads. Other private data release schemes includethose based on multiplicative weights, maximum entropy, compressive sensingand sparse summaries. However, there do not exist any fair comparisons of the stateof-the-art to show “best in class” algorithms and some problems remain open. Thisthesis’s objective is three-fold. First, it surveys the best-known methods for linearcounting queries and private data release. Second, it does a comparative study of thebest practical mechanisms for the linear counting problem under differential privacy.Third, it points out some remaining challenges and proposes several techniques toovercome them.