PaperlayerView exact revision on arXiv

Source-linked AI summary

PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions

Jun Zhang, Xiaokui Xiao, Xing Xie

arXiv:1601.03229v2cs.DB

TL;DR

Existing private hierarchical decompositions must choose a maximum depth because their noise scales with that depth, creating a granularity–accuracy dilemma. PrivTree removes this dependency through depth-independent constant noise for split decisions, extends the approach to spatial and sequence data, and significantly outperforms prior methods in data utility.

  • Problem

    Private hierarchical decomposition must approximate tuple distributions while choosing a maximum depth h that controls both granularity and noise.

  • Method

    PrivTree uses a differentially private hierarchical decomposition with constant noise for deciding whether to split a sub-domain, and applies it to spatial and sequence data.

  • Results

    PrivTree significantly outperforms the state of the art in data utility across experiments on varied real datasets.

  • Takeaways & Limitations

    PrivTree provides a general approach for hierarchical decomposition that removes the constraint of a predefined tree height and supports spatial and sequence data release.

  • Takeaways & Limitations

    The sequence extension assumes a known maximum sequence length; if unknown, sequences must be truncated to a chosen bound.

Abstract

from arXiv · show

Given a set D of tuples defined on a domain Omega, we study differentially private algorithms for constructing a histogram over Omega to approximate the tuple distribution in D. Existing solutions for the problem mostly adopt a hierarchical decomposition approach, which recursively splits Omega into sub-domains and computes a noisy tuple count for each sub-domain, until all noisy counts are below a certain threshold. This approach, however, requires that we (i) impose a limit h on the recursion depth in the splitting of Omega and (ii) set the noise in each count to be proportional to h. This leads to inferior data utility due to the following dilemma: if we use a small h, then the resulting histogram would be too coarse-grained to provide an accurate approximation of data distribution; meanwhile, a large h would yield a fine-grained histogram, but its quality would be severely degraded by the increased amount of noise in the tuple counts. To remedy the deficiency of existing solutions, we present PrivTree, a histogram construction algorithm that also applies hierarchical decomposition but features a crucial (and somewhat surprising) improvement: when deciding whether or not to split a sub-domain, the amount of noise required in the corresponding tuple count is independent of the recursive depth. This enables PrivTree to adaptively generate high-quality histograms without even asking for a pre-defined threshold on the depth of sub-domain splitting. As concrete examples, we demonstrate an application of PrivTree in modelling spatial data, and show that it can also be extended to handle sequence data (where the decision in sub-domain splitting is not based on tuple counts but a more sophisticated measure). Our experiments on a variety of real datasets show that PrivTree significantly outperforms the states of the art in terms of data utility.

1. INTRODUCTION

The paper frames private hierarchical decomposition as a trade-off between granularity and noise, then introduces PrivTree to remove the need for a preset recursion depth. It applies the approach to spatial and sequence data and reports improved utility over prior methods.

  • Motivation: Existing hierarchical methods recursively split domains and add noise proportional to a preset maximum depth h, which must be fixed before execution.The depth is needed to determine the noise amount required for differential privacy.
  • Motivation: Fine-grained decompositions require large h, but larger h increases noise and causes more errors when deciding whether to split domains.The resulting dilemma prevents any choice of h from reliably producing an accurate approximation.
  • Motivation: Heuristics for selecting h or obtaining fine-grained decompositions are rather ineffective on skewed input distributions.The paper notes that skewed distributions are often encountered in practice.
  • PrivTree: PrivTree uses constant noise for split decisions, eliminating dependence on a predefined recursion-depth threshold.Its privacy mechanism analyzes Laplace noise to obtain a tight privacy bound and enable depth-independent publication of split decisions.
  • Applications and evaluation: PrivTree is applied to spatial and sequence data, including sequence splitting decisions based on a sophisticated measure rather than tuple counts.Experiments on varied real datasets report considerable utility improvements over the state of the art.
  • Analysis: The paper analyzes PrivTree’s connection to support vector techniques and proves that a relevant SVT variant does not satisfy differential privacy.This makes that variant inapplicable for implementing PrivTree in the stated context.

2. PRELIMINARIES

The preliminaries define differential privacy and its composition, introduce Laplace noise and sensitivity, and explain spatial decompositions and quadtree range counting. Quadtrees adapt their depth to data density, supporting efficient query processing and uniform estimates within leaves.

  • Differential privacy: Differential privacy requires outputs to reveal little information about whether any particular tuple is present, formalized over neighboring datasets.Neighboring datasets differ by insertion of one tuple, and ε-differential privacy bounds output-probability ratios for such datasets.
  • Noise and sensitivity: The Laplace mechanism releases a function by adding independent Laplace noise, with privacy determined by the function’s sensitivity and the noise scale.Sensitivity measures the maximum L1 change in output caused by inserting or removing one tuple.
  • Differential privacy: Sequential composition combines privacy losses: k mechanisms with ε_i guarantees provide a total guarantee based on the sum of their ε_i values.The composition rule supports analyzing algorithmic components separately before establishing an overall privacy guarantee.
  • Spatial decompositions: A spatial decomposition is a tree-structured partition of a domain into regions, with data points assigned among the tree’s leaves.The illustrated decomposition contains nine nodes associated with sub-domains of the spatial domain.
  • Range queries: Range-count traversal ignores disjoint nodes, uses stored counts for fully contained regions, descends through partial intersections, and inspects points in intersecting leaves.For the illustrated query, only four nodes need examination.
  • Spatial decompositions: Quadtrees recursively subdivide dense regions while leaving sparse regions shallow, adapting their structure to the underlying data distribution.This adaptiveness motivates their use for private spatial data summaries.
  • Range queries: For a partially intersecting leaf, assuming uniform point distribution estimates its query contribution from the noisy count and region area.Adaptive subdivision makes this assumption relatively accurate because strongly skewed leaves should have been split further.

3. PRIVATE SPATIAL DECOMPOSITIONS

This section develops PrivTree, a hierarchical spatial decomposition method that removes the preset recursion-depth limit by using biased counts and depth-independent noise for split decisions. It also establishes privacy and utility properties and outlines extensions beyond quadtrees and tuple counts.

  • Limitations of Prior Methods: Existing private quadtrees require a maximum height h, with Laplace noise scale λ ≥ h/ε, creating a trade-off between granularity and split-decision accuracy.Small h restricts adaptation to the data distribution, while large h increases noise and errors.
  • Privacy Analysis: A non-trivial Laplace-noise analysis shows that PrivTree can use a constant noise amount independent of recursion depth while satisfying differential privacy.The paper states ε-differential privacy when λ meets the theorem’s parameter condition.
  • The PrivTree Algorithm: PrivTree removes the preset height threshold and constructs a quadtree by recursively splitting nodes according to noisy biased counts.The algorithm takes λ, a split threshold θ, and a positive parameter δ, but no maximum tree height h.
  • The PrivTree Algorithm: PrivTree biases each node count as b(v) = c(v) − depth(v) · δ, floors it at θ − δ, adds Laplace noise, and splits when the noisy value exceeds θ.The depth-dependent bias replaces direct noise calibration to the recursion depth.
  • Utility and Parameterization: PrivTree’s expected tree size is at most twice the noiseless tree size when the latter has more than one node.This guarantee applies when δ = λ·ln β, where β is the tree fanout.
  • Extensions: The framework extends to non-quadtree structures and to monotonic score functions, supporting private synopses for mixed numeric-categorical data and sequence modeling.For sequence data, splitting can use a monotonic suitability score rather than tuple counts.

4. PRIVATE MARKOV MODELS

The paper extends PrivTree to private Markov models for sequence data by representing sequences with prediction suffix trees and using a score-based splitting rule instead of tuple counts. The resulting construction preserves differential privacy and supports sequence queries and synthetic-data generation.

  • Markov models and PSTs: A prediction suffix tree represents a Markov model with predictor strings at nodes and symbol-count histograms for predicting the next symbol.Each node’s histogram counts symbols following occurrences of its predictor string.
  • Markov models and PSTs: PST nodes form a hierarchy in which each child has a longer predictor string, enabling increasingly specific next-symbol predictions.A child is created by prepending a symbol to its parent’s predictor string.
  • PST operations: A PST estimates query-string frequencies by multiplying root counts with conditional next-symbol probabilities selected from the longest matching suffix nodes.The procedure traverses query prefixes and uses each selected histogram’s magnitude and symbol counts.
  • PST operations: PSTs can generate synthetic sequences by repeatedly selecting the longest matching suffix node, sampling its next symbol, and stopping at the end marker.Generation starts from the initial marker and iterates until the sampled symbol is the sequence terminator.
  • Private PST construction: PrivTree adapts hierarchical decomposition to PSTs by replacing tuple counts with a score based on domain structure, histogram magnitude, and entropy.The score is designed to be monotonic, while small histogram magnitude or entropy favors stopping; domains beginning with the start marker cannot be split.
  • Private PST construction: The construction assumes a known maximum sequence length or truncates longer sequences, and its modified PrivTree and leaf-count postprocessing satisfy ε-differential privacy under stated parameter conditions.Theorem 4.1 requires λ ≥ 2β−1/ε with β = |I|+1; Theorem 4.2 requires λ ≥ l⊤ for postprocessing.
  • Comparison with previous work: Compared with prior sequence-publishing methods, PrivTree avoids dependency on a pre-defined recursion-depth threshold and uses three splitting conditions rather than only node counts.The paper presents experiments as evidence of its effectiveness for sequence-data modeling.

5. CONNECTIONS TO SVT

The paper analyzes PrivTree’s relationship to sparse vector techniques, focusing on a binary SVT privacy claim used by prior work. It shows that the claim fails in the worst case, invalidating binary-SVT-based solutions for this setting.

  • SVT background: Sparse vector techniques process counting queries against a threshold and output either likely-above-threshold queries or noisy answers for them.The paper frames SVTs as conceptually similar to PrivTree because both make threshold-style decisions.
  • Prior privacy claim: A prior claim asserted that binary SVT needs noise scale Θ(1/ε), independent of the number of queries.Under that claim, binary SVT could have provided a competitive implementation for hierarchical decomposition.
  • Prior privacy claim: The proposed binary-SVT construction would recursively split nodes when noisy counts exceed a threshold and append child-count queries dynamically.The claimed privacy guarantee would have applied to the resulting decomposition with a constant noise scale.
  • Privacy analysis: In the worst case, binary SVT requires noise λ = Ω(k/ε), where k is the number of queries, contradicting the claimed query-independent scale.The paper gives a sequence of k count queries for which privacy is violated when λ is too small.
  • Privacy analysis: This result invalidates prior binary-SVT-based solutions, while another SVT variant also violates differential privacy and the remaining variant is not competitive for the problem.The paper therefore finds the analyzed SVT alternatives unsuitable for implementing PrivTree in this context.

6. EXPERIMENTS

The experiments evaluate PrivTree for private spatial and sequence-data modelling against state-of-the-art baselines. Across spatial datasets and query workloads, PrivTree generally achieves the best utility, with especially strong performance on skewed data.

  • Spatial data: The evaluation compares PrivTree with UG, AG, Hierarchy, DAWA, and Privelet* for private spatial-data modelling.The methods are assessed through private synopses and range count queries.
  • Spatial data: Each spatial dataset uses small, medium, and large sets of 10,000 randomly generated range count queries.The query regions cover [0.01%, 0.1%), [0.1%, 1%), and [1%, 10%) of the data domain, respectively.
  • Spatial data: On road, PrivTree significantly outperforms UG, AG, Hierarchy, and Privelet* across query sets and privacy budgets.DAWA is the closest competitor but remains worse than PrivTree, reaching 2 to 3 times higher relative error in specified settings.
  • Spatial data: On Gowalla, PrivTree consistently achieves the best results, although performance gaps narrow because the dataset is less skewed than road.DAWA remains noticeably inferior on the small and medium query sets.
  • Spatial data: On NYC and Beijing, PrivTree outperforms the other methods, including on highly skewed NYC and less skewed Beijing.Its tree grows tall in dense regions and short in sparse regions, while Hierarchy is omitted because its four-dimensional tree requires at least 2.18 billion leaf nodes.
  • Sequence data: The sequence experiments compare PrivTree with N-gram and EM for top-k frequent string mining on mooc and msnbc.Precision is evaluated for the returned top-k strings; Truncate is included as a non-private reference approach.
  • Sequence data: PrivTree consistently outperforms N-gram and EM, and exceeds Truncate in precision when ε ≥0.8.Its Markov model can recover information lost through sequence truncation, while N-gram is more than 10% lower than PrivTree in most settings.
  • Sequence data: PrivTree has small total variation-distance error comparable to Truncate, especially when ε ≥0.2, whereas N-gram has enormous error in all cases.The authors conclude that PrivTree is preferable to N-gram for differentially private sequential-data modelling.

7. ADDITIONAL RELATED WORK

The paper situates PrivTree among differential-privacy methods for spatial and sequence modeling, aggregate-query processing, and broader private-data tasks.

  • Prior work includes private spatial decomposition using uniform grids and private k-d trees over grid cells.
  • Aggregate-query methods release marginals, data cubes, or workload-optimized data representations under differential privacy.
  • DAWA is reported as being outperformed by PrivTree on relative errors for spatial range-count queries.
  • Differential privacy has also been applied to regression, clustering, decision trees, recommendation systems, time-series analysis, optimization, itemset mining, and graph queries.

8. CONCLUDING REMARKS

The paper removes the need to predefine decomposition-tree height by controlling split decisions with bias, then applies PrivTree to spatial and sequence data release.

  • PrivTree addresses the dilemma of choosing the maximum height h in differentially private hierarchical decomposition.
  • The method removes the constraint on h by introducing carefully controlled bias when deciding whether to split a node.
  • Experiments show that PrivTree significantly outperforms state-of-the-art methods in data utility.
  • Future work proposes extending the idea to lattice-based problems such as frequent itemset mining.

A. ADDITIONAL ANALYSIS ON SVT

The SVT analysis distinguishes several variants, establishes privacy-cost limitations for existing forms, and explains why improved SVT remains less suitable than PrivTree for hierarchical decomposition.

  • The paper analyzes vanilla, reduced, and improved sparse vector techniques, with improved SVT using one noisy threshold throughout.
  • Improved SVT satisfies ε-differential privacy when its noise scale λ is at least 2/ε.
  • Existing reduced and improved SVT variants require Laplace noise proportional to t in each query answer, limiting their competitiveness for hierarchical decomposition.
  • PrivTree instead requires Laplace noise of scale Θ(1/ε) when deciding whether a node should be split.

B. PROOFS

The proofs establish privacy and structural properties of PrivTree and analyze the probability and noise behavior underlying its decomposition guarantees.

  • The proofs establish PrivTree’s main theorem from the privacy analysis in Section 3.3.
  • For sequence data, appending a symbol changes histogram counts only along nodes whose predictor strings are suffixes of the preceding sequence.
  • The analysis uses monotonicity of node scores and the property that affected nodes form a root-to-leaf path with score changes of at most one.
  • The improved SVT privacy proof bounds neighboring-dataset output probabilities by e^ε when λ ≥ 2/ε.
  • The proofs analyze neighboring datasets by comparing counting-query behavior under tuple insertion and using monotonicity of Laplace-noise tail probabilities.

C. ADDITIONAL EXPERIMENTS

Additional experiments examine computation cost, fanout and tree-height choices across PrivTree and comparison methods. They find that smaller fanout can slightly increase PrivTree query error, while recommended height settings are generally strong for Hierarchy and N-gram.

  • Computation efficiency: PrivTree’s computation cost increases with ε and is higher on the larger road and msnbc datasets.The reported processing times are averaged over 100 runs.
  • Fanout: Decreasing PrivTree’s fanout generally slightly increases query error because it produces taller trees and larger depth-dependent bias terms.The bias term is depth(v)·δ, subtracted from each node score during splitting decisions.
  • Fanout: On some NYC and Beijing settings, β = 2^d/2 yields smaller errors than β = 2^d because large fanout can amplify incorrect splits and create noise-dominated child nodes.Large fanout divides a low-count node into more children, each with a smaller count.
  • UG: UG has no single grid parameter r that consistently wins, but r = 1 is among the best overall choices and supports the recommended m setting.UG’s error does not always vary monotonically with ε because m changes with ε.
  • Tree height: Hierarchy uses heuristically selected fanout and height, with β = 64 and h = 3 for two-dimensional data; four-dimensional settings would yield prohibitively many leaf nodes.The two-dimensional decomposition uses 8 × 8 child nodes, while the four-dimensional heuristic gives β = 1296 and h = 4.
  • Tree height: Hierarchy’s recommended tree height is generally its best choice, while N-gram’s recommended h = 5 provides one of its best overall results, with h = 4 close behind.Hierarchy is evaluated with h from 3 to 8, and N-gram with h from 3 to 7.
Loading 1601.03229v2…