Residual Sensitivity for Differentially Private Multi-Way Joins

A general-purpose query engine that supports a large class of SQLs under differential privacy is the holy grail in privacy-preserving query release. The join operator presents a major difficulty towards realizing this goal, since a single tuple may affect a large number of query results, and the problem worsens as more relations are involved in the join. The traditional approach of global sensitivity fails to work as it assumes pessimistically that every pair of tuples from two different relations may join. To address the issue, instance-dependent sensitivity measures have been proposed, but so far none has met the following three desiderata for it to be truly practical: (1) the released answer should have low noise levels (i.e., high utility); (2) it can be computed efficiently; and (3) the method can be easily integrated into an existing relational database. This paper presents the first differentially private mechanism for multi-way joins that satisfies all three desiderata while supporting any number of private relations, moving us one step closer to a full-featured query engine for private relational data.