Privacy Budget Allocation in Hierarchical Data Structures

109 concepts62 papers1 proposal

When releasing sensitive datasets—such as geographic distributions, web analytics, or census data—we often organize the data hierarchically. A spatial dataset might be partitioned using a quadtree, while demographic data naturally follows a geographic spine (e.g., Country $\rightarrow$ State $\rightarrow$ County $\rightarrow$ Tract).

To guarantee differential privacy, we must inject random noise into the queries or counts at each node of these structures. However, we face a fundamental constraint: the total privacy budget (expressed as $\epsilon$) is finite. If we partition data deeply to achieve high resolution, we must distribute this limited budget across multiple levels of the hierarchy.

The Height Dilemma and Budget Starvation

If we allocate the privacy budget uniformly across all levels of a tree, we run into what Jun Zhang et al. describe as a fundamental conflict between resolution and noise in PrivTree: A Differentially Private Algorithm for Hierarchical Decompositions. As a tree grows deeper to capture fine-grained details, the budget allocated to each individual level shrinks. Consequently, the cumulative noise required to maintain differential privacy across the entire path increases with the tree's height. At the leaf nodes—where the true data counts are already small—this accumulated noise easily drowns out the actual signal.

This trade-off creates a phenomenon known as the budget starvation effect. As explored by Ritesh Ahuja et al. in A Utility-Preserving and Scalable Technique for Protecting Location Data with Geo-Indistinguishability, if a mechanism spends too much of its privacy budget at higher levels of a hierarchy to ensure accurate global routing, it leaves an insufficient budget for fine-grained leaf nodes. Conversely, if it under-spends at the top, the system makes incorrect high-level structural selections. The result is a U-shaped utility curve where increasing the resolution of a data structure eventually degrades overall data accuracy.

Non-Uniform and Adaptive Allocation

To prevent budget starvation, researchers use non-uniform allocation strategies. The core intuition relies on the inherent properties of a hierarchy: higher-level nodes aggregate large populations, meaning they naturally possess a high signal-to-noise ratio. Leaf nodes contain far fewer records, meaning they require a larger share of the privacy budget to keep noise within a useful bound.

Uniform Allocation:
Level 0 (Root)  |==| (Budget: ε/3) -> High population, low relative noise
Level 1 (Mid)   |==| (Budget: ε/3)
Level 2 (Leaf)  |==| (Budget: ε/3) -> Small population, high relative noise (Drowned out!)

Adaptive Allocation:
Level 0 (Root)  |=|   (Budget: ε/6) -> High population tolerates more noise
Level 1 (Mid)   |==|  (Budget: ε/3)
Level 2 (Leaf)  |===| (Budget: ε/2) -> Larger budget protects granular details

Rui Chen et al. applied this strategy to transaction logs in Publishing Set-Valued Data via Differential Privacy, adaptively increasing the budget for deeper, more specific nodes in a taxonomy tree. By shifting the budget downward, the granular data remains useful for counting queries despite the decreasing number of records per partition. Similarly, Sina Shaham et al. demonstrate in Differentially-Private Publication of Origin-Destination Matrices with Intermediate Stops that allocating a smaller portion of the budget to higher-level nodes captures the general data shape, while reserving the majority for leaf nodes ensures high accuracy for specific counts.

Rather than just shifting flat percentages, we can also scale the noise dynamically based on tree depth. In Facility Location Problem in Differential Privacy Model Revisited, Di Wang et al. show that scaling privacy-preserving noise exponentially relative to the depth of a hierarchical tree ensures that the total privacy budget is respected without the noise overwhelming the connection costs at lower levels. Taking this concept further, Junfeng He demonstrates in Differentially Private Heatmaps that a hierarchical noise scaling strategy that decays noise magnitude across levels can eliminate the logarithmic error penalty typically found in standard hierarchical aggregation techniques.

Algorithmic Optimization of the Budget

Instead of relying on manual heuristics, modern frameworks formalize budget distribution across a hierarchy as an optimization problem.

In Optimizing Hierarchical Queries for the Attribution Reporting API, Matthew Dawson et al. introduce a greedy iterative strategy to minimize total estimation error. Their algorithm allocates the privacy budget across different levels of a hierarchy by prioritizing levels where budget increases yield the most significant reductions in variance. Crucially, the authors show that historical noisy data can be leveraged as a prior to optimize this allocation for current queries without consuming additional privacy budget or violating privacy guarantees.

For spatial histograms, Sina Shaham et al. develop a mathematical solution in HTF: Homogeneous Tree Framework for Differentially-Private Release of Location Data. They utilize convex optimization to distribute privacy budgets non-uniformly across a hierarchy, explicitly prioritizing lower tree levels to mitigate the relative impact of noise on small data counts.

Structural vs. Quantitative Allocation

A hidden trap in hierarchical differential privacy is that the tree structure itself can leak information. If you use the underlying data to decide where to split a node (e.g., building a data-dependent quadtree or kd-tree), that structural decision costs privacy budget.

As highlighted by the authors of HTF, data-dependent spatial indexing requires allocating a portion of the privacy budget to define partition boundaries, which reduces the budget available for reporting the actual data counts.

To resolve this trade-off, Fumiyuki Kato et al. in HDPView: Differentially Private Materialized View for Exploring High Dimensional Relational Data and Xue Meng et al. in Different strategies for differentially private histogram publication show that strategically investing a portion of the budget into optimizing data partitioning pays off. Even though it leaves less budget for the final data values, the resulting structural efficiency ensures that the partitions better capture the underlying data distribution, more than compensating for the increased noise per bin.

The Local Differential Privacy Paradigm Shift

The mathematics of budget allocation changes completely when moving from a centralized model to Local Differential Privacy (LDP), where individual users perturb their own data before sending it to an aggregator.

In decentralized environments, splitting a fixed privacy budget across multiple levels of a tree dilutes the signal-to-noise ratio to a catastrophic degree. To circumvent this limitation, Tejas Kulkarni et al. propose a sampling approach in Answering Range Queries Under Local Differential Privacy.

Instead of dividing their budget across the hierarchy, users report data for a single randomly selected level of the hierarchical tree using their full privacy budget. This prevents budget fragmentation, maintains high signal quality per report, and allows the central aggregator to accurately reconstruct the global hierarchy from the collection of single-level reports.

Key Foundational Work

Frequent grams based embedding for privacy preserving record linkage (2012) — contributed 3 concept elements to this direction.
Differentially Private Spatial Decompositions (2011) — contributed 2 concept elements to this direction.
Differentially Private Spatial Decompositions (2012) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 56 papers
  2. Version 1 · 2026-10-04 · 38 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_hierarchical_privacy_budget_allocation_42c1b50e,
  title = {hierarchical privacy budget allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hierarchical-privacy-budget-allocation/rdr_42c1b50e28894560a45b548396435e8f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_hierarchical_privacy_budget_allocation_42c1b50e_v2,
  title = {hierarchical privacy budget allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hierarchical-privacy-budget-allocation/rdr_42c1b50e28894560a45b548396435e8f/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake