PaperlayerView exact revision on arXiv

Source-linked AI summary

Differential Privacy via Wavelet Transforms

Xiaokui Xiao, Guozhang Wang, Johannes Gehrke

arXiv:0909.5530v1cs.DB

TL;DR

Existing privacy-preserving publishing methods can provide weak utility for aggregate count queries, especially when query noise grows with dataset size. Privelet applies wavelet transforms before adding noise to ensure ε-differential privacy while improving range-count-query accuracy, with theoretical and experimental support.

  • Problem

    Existing ε-differentially private publishing methods can yield Θ(m) noise variance for aggregate count queries over a constant fraction of frequency-matrix entries.

  • Method

    Privelet applies an invertible wavelet transform to the frequency matrix, adds Laplace noise to the resulting coefficients, and reconstructs the published data.

  • Results

    Privelet provides improved theoretical range-count-query accuracy and experimentally demonstrates effectiveness and efficiency; Privelet+ has smaller query error than Basic when coverage exceeds 1% or selectivity is at least 10^-7.

  • Takeaways & Limitations

    Wavelet-based publishing can preserve ε-differential privacy while providing accurate range-count answers for ordinal and nominal data.

  • Takeaways & Limitations

    Privelet can be inferior to Dwork et al.’s method in practice when input tables contain attributes with small domains.

Abstract

from arXiv · show

Privacy preserving data publishing has attracted considerable research interest in recent years. Among the existing solutions, {\em $ε$-differential privacy} provides one of the strongest privacy guarantees. Existing data publishing methods that achieve $ε$-differential privacy, however, offer little data utility. In particular, if the output dataset 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 {\em 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 {\em 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.

I. INTRODUCTION

Privacy-preserving publication must balance protection of sensitive records with useful statistical answers. The paper targets poor utility for large range-count queries by introducing Privelet, which combines differential privacy with wavelet transforms.

  • Sensitive organizational data has research value, but releasing it requires modifications that protect contributors while retaining statistical characteristics.
  • ε-differential privacy makes conservative assumptions about an adversary’s background knowledge and limits information inferred about individuals.
  • Motivation: Θ(m) noise variance makes large aggregate-query answers potentially meaningless when the frequency matrix contains m entries.Dwork et al.’s method adds independent noise to frequency-matrix entries, so queries covering a constant fraction of entries accumulate Θ(m) variance.
  • Our Contributions: Privelet ensures ε-differential privacy while providing accurate answers for all range-count queries.Range-count queries use intervals for ordinal attributes and hierarchy-based leaf or subtree sets for nominal attributes.
  • Our Contributions: Privelet applies a wavelet transform to the frequency matrix, adds noise to the transformed coefficients, and maps the result back to a noisy matrix.The paper develops instantiations for ordinal and nominal data and analyzes their privacy, utility, and time-complexity guarantees.

B. Previous Approaches

The paper contrasts direct noise addition to frequency matrices with Privelet’s transformed-domain approach. Its framework uses weighted noise on wavelet coefficients to preserve differential privacy while improving range-query utility.

  • Previous Approaches: Dwork et al.’s method adds independent Laplace noise to each frequency-matrix entry and provides 2/λ-differential privacy.The frequency matrix has sensitivity 2 because changing one tuple changes two entries by one.
  • Previous Approaches: Θ(m/ε^2) worst-case query-error variance makes direct frequency-matrix perturbation unsatisfactory for range queries covering many entries.Each entry has variance 8/ε^2, and a range-count query may cover up to m entries.
  • Privelet Framework: Privelet transforms frequency matrix M into coefficient matrix C, adds independent Laplace noise, optionally refines C, and reconstructs noisy matrix M ∗.The refinement depends only on noisy coefficients, not on the original table or frequency matrix.
  • Privacy Condition: Changing one input tuple induces linear changes in wavelet coefficients because each coefficient is a linear combination of frequency-matrix entries.This motivates concealing coefficient changes with appropriately calibrated noise.
  • Privacy Condition: For generalized sensitivity ρ and weight function W, Privelet achieves ε-differential privacy by adding Laplace noise of magnitude 2ρ/W(c) to coefficient c.The framework assigns smaller noise magnitude to coefficients with larger weights.

IV. PRIVELET FOR ONE-DIMENSIONAL ORDINAL DATA

Privelet instantiates its framework with the one-dimensional Haar wavelet transform for ordinal data, adding weighted noise to wavelet coefficients before reconstructing a noisy frequency matrix. This preserves ε-differential privacy while bounding range-count query noise polylogarithmically in the matrix size.

  • One-Dimensional Haar Wavelet Transform: The one-dimensional Haar wavelet transform applies to a frequency vector with 2^l totally ordered entries and produces wavelet coefficients from a binary decomposition tree.The transform also produces a base coefficient from the entries’ aggregate.
  • One-Dimensional Haar Wavelet Transform: Each frequency-matrix entry can be reconstructed from the base coefficient and its ancestors, using signs determined by the entry’s subtree positions.For the Figure 2 example, v2 = 3 = c0 + c1 + c2 − c4.
  • Instantiation of Privelet: Privelet adds Laplace noise to each Haar coefficient with magnitude λ/WHaar(c), using larger weights for coefficients with lower query sensitivity.The base coefficient receives weight m, while a level-i coefficient receives weight 2^(l−i+1).
  • Instantiation of Privelet: The one-dimensional Haar transform has generalized sensitivity 1 + log2 m because changing one matrix entry affects only that entry’s coefficient path and the base coefficient.The affected path contains the base coefficient and all ancestors of the changed entry.
  • Instantiation of Privelet: With ε = 2(1 + log2 m)/λ, Privelet ensures ε-differential privacy, while any range-count query has noise variance at most (2 + log2 |M*|)σ^2/2.Combining the privacy and utility lemmas yields a polylogarithmic noise-variance bound, improving over Dwork et al.’s O(m/ε^2) bound.
  • Instantiation of Privelet: Construction takes O(n + m) time, including frequency-matrix construction, Haar transformation and inversion, and coefficient noise injection.Each transform and noise-injection stage contributes O(m) overhead after mapping the table to the matrix.

V. PRIVELET FOR ONE-DIMENSIONAL NOMINAL DATA

For one-dimensional nominal data, Privelet replaces ordinal wavelets with a hierarchy-based nominal wavelet transform. The method addresses high-fanout hierarchies without pairwise subtree comparisons, while mean subtraction supports its utility guarantee.

  • Nominal Wavelet Transform: Existing wavelet transforms require totally ordered domains, so they are not directly applicable to nominal attributes.Imposing an artificial order can make nominal hierarchy-defined predicates contiguous, but the paper develops a dedicated transform instead.
  • Nominal Wavelet Transform: The transform avoids generating pairwise subtree coefficients when a hierarchy node has many children, addressing the resulting coefficient-growth problem.This design answers whether coefficients can be generated without relying on pairwise comparisons of subtrees.
  • Nominal Wavelet Transform: The nominal wavelet transform constructs a decomposition tree from the attribute hierarchy and computes coefficients for its internal nodes, including a root leaf-sum coefficient.Each hierarchy leaf receives a child whose value equals the corresponding frequency-matrix entry.
  • Nominal Wavelet Transform: Each nominal frequency entry is reconstructed from its ancestors using their coefficients and fanouts in the decomposition tree.The paper gives the reconstruction relation through the leaf-sums of successive ancestors.
  • Nominal Wavelet Transform: The nominal transform is over-complete: it generates m′ coefficients for m input entries, with the excess equal to the hierarchy’s number of internal nodes.The paper states that this overhead is usually negligible when internal nodes are few relative to leaves.
  • Instantiation of Privelet: Privelet injects Laplace noise according to fanout-based weights, then subtracts sibling-group means before reconstructing the noisy frequency matrix.Mean subtraction makes noisy coefficients within each sibling group sum to zero and is essential to the utility guarantee.

C. Theoretical Analysis

The analysis establishes privacy and utility guarantees for Privelet’s nominal wavelet transform, including bounded range-query noise and improved practical performance over the Haar transform.

  • Privacy guarantee: The nominal wavelet transform has generalized sensitivity h, where h is the associated hierarchy’s height.This sensitivity result supports the transform’s privacy analysis.
  • Privacy guarantee: Given parameter λ, the nominal instantiation ensures (2h/λ)-differential privacy for one-dimensional nominal tables.The guarantee follows by combining the sensitivity result with the framework’s privacy lemma.
  • Utility guarantee: For any range-count query, reconstructing the noisy matrix yields answer noise variance less than 4σ².The bound assumes coefficient noises have variance at most (σ/WNom(c′))² and uses mean subtraction before reconstruction.
  • Efficiency: The nominal-wavelet implementation runs in O(n + m) time.Its stages include frequency-matrix construction, transformation, noise injection, and reconstruction.
  • Practical comparison: For the Brazil census Occupation attribute, the nominal transform provides a 15-fold reduction in noise variance over the straightforward HWT.The comparison uses a domain with m = 512 leaves and a hierarchy with 3 levels.

VI. MULTI-DIMENSIONAL PRIVELET

The multi-dimensional Privelet extension applies one-dimensional wavelet transforms successively across dimensions, propagates their weights, adds scaled Laplace noise, and reconstructs the frequency matrix by inversion.

  • Multi-dimensional transform: The multi-dimensional extension applies one-dimensional transforms along each dimension in turn, producing successive step-i matrices.Each matrix Ci becomes the input for transformation along the next dimension.
  • Multi-dimensional transform: Figure 4 illustrates the HN transform on a two-dimensional frequency matrix by transforming vectors first along one dimension and then along the other.The final matrix C2 contains the resulting coefficients.
  • Noise injection and reconstruction: Privelet adds Laplace noise of magnitude λ/WHN(c) to each coefficient and reconstructs M* by inverting transforms from dimension d through dimension 1.For nominal dimensions, mean subtraction is applied before reconstruction.
  • Weight construction: The HN weight WHN(c) is computed by multiplying the per-dimension weight for each transform step by the shared weight inherited from earlier steps.All coefficients in a source vector share a weight because of the step-wise arrangement.
  • Weight construction: In the two-dimensional nominal example, a step-1 base coefficient has weight 1/2, while the step-2 base coefficient c11 has weight 1/4.The second value results from multiplying the inherited 1/2 weight by the second transform’s 1/2 base-coefficient weight.

C. Theoretical Analysis

The theoretical analysis establishes privacy and utility guarantees for Privelet and Privelet+, including hybrid handling of attributes with different domain sizes. Privelet+ preserves differential privacy while improving range-count accuracy and retaining linear-time processing.

  • The HN wavelet transform has generalized sensitivity proportional to the product of P(A_i) across the d dimensions.
  • For range-count queries, the HN-based Privelet noise variance is bounded using the product of H(A_i) across dimensions.
  • Privelet+ partitions the frequency matrix by selected attributes, applies lower-dimensional HN transforms to each sub-matrix, and recombines the noisy results.
  • Privelet+ achieves ε-differential privacy with a guarantee determined by the product of P(A) over attributes excluded from wavelet processing.
  • Privelet+ is no worse than Privelet and Dwork et al.’s method when selected attributes satisfy the stated domain-size condition.
  • Privelet+ runs in O(n + m) time, while its hybrid design addresses datasets containing both large- and small-domain attributes.

VII. EXPERIMENTS

Experiments on large Brazil and US census datasets compare Privelet+ with Basic under differential privacy across range-count query workloads. Privelet+ generally achieves substantially lower query error, especially for queries with larger coverage or sufficient selectivity.

  • Experimental Setup: Experiments use Brazil and US census datasets containing 10 million and 8 million tuples, respectively, with ordinal and nominal attributes.
  • Experimental Setup: The evaluation uses 40,000 random range-count queries per dataset, grouped by query coverage and selectivity.
  • Accuracy of Range-Count Queries: Basic’s average square error increases linearly with query coverage, while Privelet+ remains insensitive to query coverage.
  • Accuracy of Range-Count Queries: Privelet+’s maximum average error is smaller than Basic’s by two orders of magnitude, and both methods improve as ε increases.
  • Accuracy of Range-Count Queries: Privelet+ has no more than 25% error in all cases, whereas Basic exceeds 70% error in several query subsets.
  • Accuracy of Range-Count Queries: Privelet+ incurs smaller query error than Basic when query coverage exceeds 1% or query selectivity is at least 10^-7.

B. Computation Time

Privelet+ scales linearly with both the number of input tuples n and the number of frequency-matrix entries m, with O(n + m) time complexity. It incurs higher computation overhead than Basic, justified by better range-count-query utility.

  • Scaling with n: Privelet+'s computation time is linear in n when m = 2^24 and n ranges from 1 million to 5 millions.In this setting, Privelet+ uses SA = ∅ and performs wavelet transforms on all frequency-matrix dimensions.
  • Scaling with m: Both techniques run in linear time with respect to m when n = 5 × 10^6 and m varies from 2^22 to 2^26.The computation-overhead comparison is shown in Figure 11.
  • Scalability: Both Basic and Privelet+ scale linearly with n and m, confirming Privelet+'s O(n + m) time complexity.Experiments vary n from 1 million to 5 millions with fixed m, and m from 2^22 to 2^26 with fixed n = 5 × 10^6.
  • Cost versus utility: Privelet+ incurs higher computation overhead than Basic but provides much better utility for range-count queries.The paper presents this overhead as justified by Privelet+'s improved query utility.
  • Overall evaluation: Privelet provides improved theoretical accuracy guarantees for range-count queries and experimentally demonstrates effectiveness and efficiency.The conclusion characterizes the overall evaluation without reporting a separate computation-time number.

APPENDIX

The appendix analyzes how wavelet-coefficient noise propagates into range-count answers for ordinal and nominal data. It bounds coefficient and query-answer variances using decomposition-tree structure and sibling-group properties.

  • Ordinal queries: A one-dimensional range-count answer is expressed as a weighted sum of wavelet coefficients whose weights depend on left- and right-subtree coverage.At each decomposition-tree level, an interval partially intersects at most two relevant coefficients.
  • Ordinal queries: For an ordinal range query, the total noise variance is bounded by (2 + log2 |M*|)/2 · σ2.The bound combines the base coefficient's contribution with at most two partially intersecting coefficients per tree level.
  • Nominal coefficients: Each non-base nominal coefficient has noise variance at most 4 · (1 − 1/f)^3 · σ2, while the base coefficient has variance at most σ2.Here f is the fanout of the coefficient's parent in the decomposition tree.
  • Nominal queries: For nominal range-count queries, answers over hierarchy subtrees can be represented using sibling groups and ancestor coefficients, with variance less than 4σ2 in the analyzed cases.The proof handles leaves, level-(h − 1) nodes, and more general hierarchy nodes by induction.

D. Proof of Theorem 2

Theorem 2 is established by relating changes in the input frequency matrix to changes through successive wavelet-transform steps. The proof proceeds inductively across transform levels.

  • Setup: The proof considers matrices differing in one input entry and tracks their corresponding step-i wavelet-transform matrices.The notation compares each transform-stage entry before and after the input change.
  • Sensitivity condition: Theorem 2 holds when the transform-stage differences satisfy the stated inequality derived from generalized sensitivity.The proof reduces the theorem to verifying this inequality for the relevant transformed matrices.
  • Induction: The argument proves the transform inequality by induction on k, beginning at k = 1 and extending from k = l to k = l + 1.The induction replaces entries in one transform stage with their counterparts and uses prior lemmas.
  • Induction step: The induction step follows from the preceding lemmas and the assigned wavelet-coefficient weights.The proof concludes once the relation is established for k = l + 1.

E. Proof of Theorem 3

Theorem 3 is proved by induction over dimensions, using linearity of the HN wavelet transform and decomposing higher-dimensional queries into lower-dimensional submatrices. The resulting query noise variance is bounded by a product involving attribute hierarchies.

  • Linearity: The HN wavelet transform is linear because it composes linear Haar and nominal wavelet transformations.This linearity yields additivity of transformed matrices and supports the theorem's induction.
  • Induction over dimensions: The proof proceeds by induction on dimension d, with the base case d = 1 and the induction step from d = k to d = k + 1.The induction reconstructs a step-k matrix by inverse transforming along the (k + 1)-th dimension.
  • Dimensional decomposition: A coefficient submatrix indexed by a fixed coordinate can be treated as a k-dimensional HN wavelet coefficient matrix and used to reconstruct a noisy lower-dimensional frequency matrix.This construction enables lower-dimensional query reasoning within the higher-dimensional proof.
  • Query decomposition: A range-count query on the full matrix is related to corresponding queries on the reconstructed submatrices, with the proof targeting a variance bound of σ2 · ∏_{i=1}^d H(Ai).The query decomposition introduces predicates on the first k dimensions in each submatrix.
  • Coefficient analysis: The proof analyzes coefficients in the transformed matrix and identifies each coefficient as representable through a range-count query on an associated vector.This connects coefficient-noise analysis to the query-answer variance bound.

SELECT COUNT(*) FROM V ∗

The section bounds noise when wavelet coefficients are reconstructed across dimensions. It uses coefficient-wise variance bounds and independence to extend the range-count query guarantee to dimension k + 1.

  • Inverse wavelet transforms reconstruct coefficients in the next-dimensional frequency matrix from the transformed representation.
  • Each reconstructed coefficient c′ is a weighted sum with noise variance at most H(Ak+1) · (σ/WHN(c′))2.
  • Independent noises across vectors and distinct coefficient assignments yield a range-count query variance no greater than σ2·Pk+1.
  • The resulting bound establishes the theorem for d = k + 1 and completes the induction.
Loading 0909.5530v1…