Empirically providing data privacy with reduced noise

Abstract

An empirical approach to providing differential privacy includes applying a common statistical query to a set of databases to produce sample values, both with and without any particular entity's data. The probability density is empirically estimated by sorting the sample values to generate an empirical cumulative distribution function. The cumulative distribution function is differenced across approximately the square root of the number of sample points to get an empirical density function. The statistical query is empirically (ε,δ)-private if the empirical densities with and without any particular individual differ by a factor of no more than exp(ε), with the exception of a set for which the densities exceed that bound by a total of no more than δ.