InfTDA: A Simple TopDown Mechanism for Hierarchical Differentially Private Counting Queries
Fabrizio Boninsegna · 2025
Read InfTDA: A Simple TopDown Mechanism for Hierarchical Differentially Private Counting Queries by Fabrizio Boninsegna (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-05347.txt.
Introduction
Fabrizio Boninsegna presents InfTDA in 2025, a simple top-down method for private counting over grouped data. Differential privacy lets analysts publish counts while mathematically limiting what can be learned about any one person. Many real queries are hierarchical: counts by country, then region, then city, each level splitting the one above.
The mechanism builds a synthetic data set from the top down that answers all such hierarchical queries with bounded error. It extends an earlier version made for trip data to any set of categorical features. Simplicity is the selling point: complex private mechanisms are hard to implement correctly. Census and mobility analysts get a tool they can deploy with confidence.
Catalog record
| CREATOR | Fabrizio Boninsegna |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-05347
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
InfTDA: A Simple TopDown Mechanism for Hierarchical Differentially Private Counting Queries Fabrizio Boninsegna Abstract This paper extends InfTDA , a mechanism proposed in (Boninsegna, Silvestri, PETS 2025) for mobility datasets with origin and destination trips, in a general setting. The algorithm presented in this paper works for any dataset of d d categorical features and produces a differentially private synthetic dataset that answers all hierarchical queries, a special case of marginals , each with bounded maximum absolute error. The algorithm builds upon the TopDown mechanism developed for the 2020 US Census. 1 Introduction Consider a dataset D\in\mathcal{X}^{n} , where the data universe \mathcal{X} is defined as the Cartesian product of d categorical features, \mathcal{X}=\mathcal{X}_{1}\times\dots\times\mathcal{X}_{d} . For example, this setting can represent a healthcare dataset with attributes such as ("medical condition", "nationality", "age", "gender"), or a geographic dataset with attributes such as ("country", "state", "city"). One of the most relevant classes of queries in these datasets is marginals. Given a subset S\subseteq[d] and specific values y_{i}\in\mathcal{X}_{i} for each i\in S , a marginal query asks: "how many records in D have, for each attribute i\in S , the value equal to y_{i} ?" The aim is to release a differentially private (DP) synthetic dataset \tilde{D} that can accurately answer all such marginal queries. InfTDA , introduced in [ 1 ] for mobility data, constructs a synthetic dataset \tilde{D} that achieves a bounded maximum absolute error of \tilde{O}(\sqrt{k^{3}d}) for any k -hierarchical query, where a k -hierarchical query is a marginal query with S=[1,\dots,k] . The algorithm employs a TopDown approach, initially developed by the US Census Bureau [ 2 ] , which leverages differentially private and optimized k -hierarchical queries as constraints to refine the estimation of (k+1) -hierarchical queries. Related Work The most straightforward method is to generate a contingency table of D , which is its histogram representation 1 1 1 The histogram representation of D is h_{D}\in\mathbb{N}_{0}^{|\mathcal{X}|} defined for each x\in\mathcal{X}_{1}\times\dots\times\mathcal{X}_{d} as h_{D}(x)=|\{y\in D:x=y\}| . , and add Gaussian noise to each count 2 2 2 It can be used also Laplace noise, however here we focus in Gaussian noise as it provides better tail bounds. . The resulting differentially private contingency table can answer all marginal queries; however, the variance grows linearly with the number of noisy counts required, leading to an absolute error of \tilde{O}(e^{(d-k)/2}) for any marginal with |S|=k . By focusing solely on k -hierarchical queries, an alternative approach would be to release a differentially private contingency table \tilde{D}_{i} for each query. In this case, each query could be answered with a maximum absolute error of \tilde{O}(\sqrt{kd}) 3 3 3 k comes from a union bound on Gaussian tails over \prod_{i=1}^{k}|\mathcal{X}_{i}|=O(2^{k}) elements. . However, this strategy requires handling d separate tables, which may be inconsistent with one another. Hay et al. [ 3 ] were the first to introduce the concept of hierarchical queries and to observe that accuracy can be improved by resolving such inconsistencies. The authors proposed a hierarchical tree structure, similar to the one defined for InfTDA , to organize the queries and developed the hierarchical mechanism, which enforces consistency through constrained optimization. A key limitation of this approach is that it produces a full DP contingency table with non-integral counts and without ensuring non-negativity. The authors identified the incorporation of non-negativity constraints as an open direction for future work. The most notable work with real-world application is undoubtedly the Disclosure Avoidance System TopDown algorithm, developed by the US Census Bureau [ 2 ] . This method follows a similar principle to the hierarchical mechanism but differs in that it does not answer all k -hierarchical queries simultaneously. Instead, queries are answered sequentially, starting from the root of the hierarchy and proceeding down the tree. The mechanism employs a more sophisticated convex optimization procedure and produces a complete differentially private contingency table \tilde{D} with non-negative and integer counts. Nevertheless, no formal utility analysis of the algorithm has been provided. An alternative method for generating general purpose synthetic DP datasets is the Multiplicative Weights Exponential Mechanism (MWEM) [ 4 ] , which is perhaps the most well-known in this category. MWEM achieves an error of \tilde{O}(\sqrt{nd}) , thus its performance is constrained by sampling error. Contributions InfTDA is a specific implementation of a hierarchical TopDown algorithm that employs constrained optimisation based on maximum error minimisation (Chebyshev distance), rather than mean squared error minimisation. The algorithm produces a differentially private contingency table \tilde{D} with non-negative integer counts and guarantees a maximum absolute error of \tilde{O}(\sqrt{k^{3}d}) for each k -hierarchical query. Intuitively, the proof shows that the error introduced by Gaussian noise accumulates linearly across the levels of the hierarchical tree. The method is scalable, as it can be executed independently on each branch of the hierarchical tree, and each privatisation mechanism runs in at most O(\max_{i}|\mathcal{X}_{i}|) time. Alongside InfTDA , Boninsegna and Silvestri [ 2 ] introduced IntOPT , an optimisation procedure that operates entirely in the integer domain and requires at most O(\max_{i}|\mathcal{X}_{i}|^{2}) steps to solve the constrained problem. 2 Preliminaries q_{S_{0}}(D) q_{S_{1},(y_{1}^{1})}(D) q_{S_{2},(y_{1}^{1},y_{2}^{1})}(D) q_{S_{2},(y_{1}^{1},y_{2}^{2})}(D) q_{S_{1},(y_{1}^{2})}(D) q_{S_{2},(y_{1}^{2},y_{2}^{1})}(D) q_{S_{2},(y_{1}^{2},y_{2}^{2})}(D) Figure 1: An example of the non-negative hierarchical tree defined by hierarchical queries for a data universe \mathcal{X}=\{y_{1}^{1},y_{1}^{2}\}\times\{y_{2}^{1},y_{2}^{2}\} . The hierarchical consistency assures that the tree is hierarchical, so that child nodes’ attributes sum to their father’s attribute. Non-Negative Hierarchical Tree A tree \mathcal{T} of depth d is a tuple \mathcal{T}=(V,E) : V=\cup_{k=0}^{d}V_{k} is the set of nodes, with V_{k} denoting the set of nodes at level k\in\{0,\dots,d\} ; E is the set of edges between consecutive levels. A node at level k is indicated with u_{k}\in V_{k} . The set of children to a node is indicated by a function \mathcal{C}:V_{k}\rightarrow 2^{V_{k+1}} for any level k\in\{0,\dots,d\} . Each node of the tree has an attribute q(u_{k}) . InfTDA works for any tree data structure defined as follows Definition 1 (Non-Negative Hierarchical Tree [ 1 ] ) . A tree \mathcal{T}=(V,E) is said to be non-negative if it contains non-negative attributes q(u)\geq 0 for any u\in V . The tree is hierarchical if the attribute of u is the sum of the attributes of its children \mathcal{C}(u) . Specifically, for every u\in V which is not a leaf, we have q(u)=\sum_{v\in\mathcal{C}(u)}q(v) . This paper focuses on integer attributes, so that q(u)\in\mathbb{N}_{0} for any u\in V . Additionally, it will be used {\bf q}_{\mathcal{C}}(u_{k}) , which is the vector containing the attributes of the children of u_{k} . Hierarchical Queries In this paper, we focus on data points containing d categorical features \mathcal{X}=\mathcal{X}_{1}\times\dots\times\mathcal{X}_{d} where each \mathcal{X}_{i} is a set of |\mathcal{X}_{i}|\geq 2 categories. A dataset consists of a multiset of n points for \mathcal{X} , thus D\in\mathcal{X}^{n} . Definition 2 (Counting Query) . A counting query is defined by a function q_{i}:\mathcal{X}\rightarrow\{0,1\} . Given a dataset D , we will abuse notation and write q_{i}(D) to denote the sum of the values of the function q_{i} on D as q_{i}(D)=\sum_{x\in D}q_{i}(x) A k -way marginal query counts the number of points in D that share the same values for a specified set of k attributes. Definition 3 ( k -way marginal query) . A k -way marginal is defined by a subset S\subseteq[d] of |S|=k