Query Answering for Tabular Data
Ryan McKenna · 2024
In this chapter, we focus on the fundamental problem of producing differentially private counts of different sub-populations (e.g., “how many individuals are 65 years or older”). In the computer science literature, these are known as counting queries . Collections of such queries are quite expressive, as they can be used to compute a wide variety of statistics, including histograms, marginals, range queries, combinations thereof, and much more. A predicate is the condition that defines the sub-population (e.g., “is 65 years or older”). A query workload is a set of counting queries in which stakeholders are interested. Our goal is to design a differentially private mechanism that answers the queries in the given input workload with low error, while preserving differential privacy.