Introduction
Differential privacy (DP) is widely regarded as the gold standard for protecting individual privacy in data sharing. However, standard DP mechanisms often rely on a critical, yet frequently overlooked, assumption: the availability of a well-defined global domain. In many real-world scenarios, such as free-text fields or large categorical sets, the domain is "weakly constrained"—it is either unknown or prohibitively large.
Applying traditional DP to these domains presents a significant challenge. If a researcher only includes values observed in the raw data in their synthetic output, they risk leaking information about rare individuals. Conversely, adding noise to every possible value in a massive domain (e.g., every possible English word) is computationally infeasible and destroys data utility. This paper introduces CatHist, an algorithm designed to handle such weakly constrained domains efficiently while maintaining rigorous privacy guarantees.
The CatHist Algorithm
The core innovation of CatHist is the move away from materializing every possible bin in a histogram. The authors first establish the Bad Bins Theorem, proving that any DP mechanism must have a non-zero probability of returning elements from outside the "active domain" (the values present in the data). Failing to do so creates a "zero-probability trap" where the absence of a value reveals its absence in the original dataset.
CatHist addresses this by analytically modeling the unrepresented part of the domain as a probability distribution. The algorithm operates through a thresholding and "pollution" process:
- Thresholding: It calculates a threshold ($\tau$) based on the domain size and a user-defined tolerance parameter, $\rho$.
- Filtering: Laplace noise is added to real category counts; those falling below $\tau$ are discarded.
- Pollution: The dataset is augmented with a mathematically determined number of random "fake" bins from the global domain, ensuring that the output distribution remains private.
Experimental Setup
The researchers evaluated CatHist using the UCI Adult dataset, focusing on three attributes: 'Sex' (small domain), 'Workclass' (long-tailed distribution), and 'Marital-status' (medium categorical domain). To simulate weakly constrained environments, they artificially expanded the domains to include hundreds of thousands or even billions of potential values (e.g., treating 'Sex' as if its domain were all English words).
Results and Discussion
The performance was measured using a Fidelity (F) metric, comparing the synthetic distribution to the original active categories.
The results highlight several key insights:
- Domain Support Matters: Attributes with high support, like 'Sex', maintained near 100% fidelity because their real counts remained significantly higher than the noise threshold.
- The Long-Tail Challenge: 'Workclass' showed lower fidelity, particularly at high privacy levels (low $\epsilon$). In long-tailed distributions, rare but legitimate values are often indistinguishable from noise and are filtered out.
- Tolerance Trade-offs: Increasing the tolerance for randomness ($\rho$) generally improved fidelity. A higher $\rho$ lowers the threshold $\tau$, allowing more low-count real categories to be preserved, albeit at the cost of including more "pollution" in the synthetic data.
Conclusion
CatHist provides a computationally efficient path for generating differentially private synthetic data in open domains. By replacing the exhaustive materialization of bins with analytical modeling, it avoids the computational pitfalls of massive domains. However, a trade-off remains: to protect privacy in large domains, users must accept a degree of "pollution" in the form of random values. Future work will explore extending this approach to continuous data and multi-dimensional correlations.
Summary updated