Differential Privacy via Wavelet Transforms

TLDR

Privacy‑preserving data publishing has attracted considerable interest, yet existing ε‑differential privacy methods provide little utility, especially for count queries where noise scales with dataset size, rendering results often useless. This paper develops a technique that guarantees ε‑differential privacy while delivering accurate range‑count query answers. The method applies wavelet transforms to the data before noise addition, with instantiations for ordinal and nominal attributes and a theoretical analysis of privacy and utility. Experiments on real and synthetic datasets demonstrate the approach’s effectiveness and efficiency.

Abstract

Privacy-preserving data publishing has attracted considerable research interest in recent years. Among the existing solutions, ∈-differential privacy provides the strongest privacy guarantee. Existing data publishing methods that achieve ∈-differential privacy, however, offer little data utility. In particular, if the output data set is used to answer count queries, the noise in the query answers can be proportional to the number of tuples in the data, which renders the results useless. In this paper, we develop a data publishing technique that ensures ∈-differential privacy while providing accurate answers for range-count queries, i.e., count queries where the predicate on each attribute is a range. The core of our solution is a framework that applies wavelet transforms on the data before adding noise to it. We present instantiations of the proposed framework for both ordinal and nominal data, and we provide a theoretical analysis on their privacy and utility guarantees. In an extensive experimental study on both real and synthetic data, we show the effectiveness and efficiency of our solution.