Privacy Budget Allocation for Hierarchical Data Release

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 238 papers59 conceptsfrozen 2026-10-04

When publishing sensitive datasets—such as GPS trajectories, census records, or web conversions—researchers face a fundamental conflict: Differential Privacy (DP) requires adding noise to data, but in high-dimensional spaces, this noise quickly overwhelms the signal. If you add noise to every possible coordinate on a map, the resulting "private" map is often just white noise.

To solve this, researchers have converged on a shared strategy: hierarchical decomposition. By organizing data into tree structures (like quadtrees or prefix trees), they can aggregate sparse data into meaningful chunks. However, the critical challenge lies in how to distribute a finite "privacy budget" ($\epsilon$) across the levels of these trees to maximize utility.

The Curse of Dimensionality and the Tree Solution

In high-dimensional settings, such as set-valued transaction logs or spatio-temporal paths, the number of possible outcomes is astronomical. Rui Chen and Benjamin C. M. Fung demonstrated that instead of treating every possible sequence as a flat category, we can use a "noisy prefix tree" or taxonomy-based partitioning to release data Differentially Private Trajectory Data Publication.

The intuition is simple: the root of the tree represents the whole dataset (high signal, low resolution), while the leaves represent specific individuals or events (low signal, high resolution). By adding noise at each level, we can protect privacy while preserving the overall structure of the data.

The Budget Allocation Dilemma

The central research question in this field is how to split the privacy budget $\epsilon$ across the tree's depth. If you spend too much budget at the top, the fine-grained details at the leaves become pure noise. If you save it all for the leaves, the structural splits at the top might be wrong, leading the entire analysis astray.

Two main strategies have emerged:

  1. Bottom-Heavy (Geometric) Allocation: Graham Cormode and colleagues found that for spatial data, increasing the budget geometrically as you move toward the leaves significantly reduces error Differentially Private Spatial Decompositions. More recently, Juba Ziani and Ferdinando Fioretto proved that "bottom-heavy" allocations are often optimal because they mitigate the bias introduced by non-negativity constraints in granular counts Optimal Allocation of Privacy Budget on Hierarchical Data Release.
  2. Top-Heavy (Decremental) Allocation: Conversely, when building decision trees or complex trajectories, the initial splits are the most critical. Kaiwen Wang and Maria-Florina Balcan argue that allocating more budget to the top levels ensures that the most influential decision nodes are accurate, preventing error propagation down the branches Scalable and Provably Accurate Algorithms for Differentially Private Distributed Decision Tree Learning.

Enforcing Consistency

A unique problem with hierarchical DP is that noisy counts at different levels often contradict each other (e.g., the sum of children might not equal the parent). To fix this, researchers use post-processing techniques like Ordinary Least Squares (OLS) or constrained inference to "smooth" the tree.

Badih Ghazi and Ravi Kumar have applied these consistency-enforcing algorithms to real-world systems like Google’s Attribution Reporting API, allowing advertisers to track conversions across hierarchies without seeing individual user actions Optimizing Hierarchical Queries for the Attribution Reporting API.

Real-World Impact: The U.S. Census

The most high-stakes application of this research is the U.S. Census. To protect the 2020 Census, the Bureau moved away from traditional "swapping" to a hierarchical DP framework. Ryan Cumings-Menon and Daniel Kifer described how they optimized the "geographic spine"—the hierarchy of states, counties, and tracts—to ensure that even small tribal areas received accurate population counts without compromising privacy Geographic Spines in the 2020 Census Disclosure Avoidance System.

By treating the privacy budget as a scarce resource to be strategically invested across a hierarchy, these researchers have turned DP from a theoretical ideal into a practical tool for large-scale data science.

Papers in this version

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 1, frozen text):

@misc{lacuna_privacy_budget_allocation_for_hierarchic_42c1b50e_v1,
  title = {Privacy Budget Allocation for Hierarchical Data Release},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/privacy-budget-allocation-for-hierarchical-data-release/rdr_42c1b50e28894560a45b548396435e8f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}