Preserving Statistical Distance via Randomized Domain Compression

24 concepts15 papers4 proposals

When analyzing large-scale datasets, we frequently encounter discrete distributions over massive alphabets. Whether tracking web traffic across millions of URLs, analyzing long text strings, or monitoring user behavior, the size of the data domain ($k$) can be overwhelmingly large.

This domain size poses a fundamental challenge when operating under real-world constraints like Differential Privacy (DP), limited communication bandwidth, or restricted memory. In a centralized, unconstrained setting, evaluating a distribution requires tracking counts for all $k$ elements. But if every user can only send a single bit, or if a streaming algorithm can only store a few kilobytes, maintaining a full histogram becomes impossible. Furthermore, under Local Differential Privacy (LDP), adding independent noise to all $k$ bins completely drowns out the statistical signal, causing the required sample complexity to explode.

To bypass this barrier, a powerful paradigm has emerged: randomized domain compression. Instead of forcing algorithms to scale with the original domain size $k$, we can use shared randomness to map the massive domain into a much smaller virtual space. Crucially, this compression acts as a statistical isometry—it shrinks the data while preserving the underlying distances between distributions, allowing us to perform complex inference tasks with minimal loss of information.


The Core Intuition: Distance-Preserving Projections

Why does mapping a massive alphabet into a handful of buckets work? The core insight lies in the geometry of probability distributions.

Suppose we want to perform identity testing: we want to determine if a sample comes from a known target distribution $P$ (such as a uniform distribution) or if it is at least $\epsilon$-far from $P$ in terms of Total Variation (TV) distance. If we randomly partition the $k$ elements of the alphabet into a much smaller number of bins, we create a compressed distribution.

If the true distribution matches $P$, its compressed version will match the compressed version of $P$. But what if the true distribution is far from $P$? As shown by Jayadev Acharya et al. in Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit, a random mapping preserves the $\ell_1$ and $\ell_2$ distances between the distributions with high probability.

Massive Domain (Size k)                 Compressed Domain (Size m << k)
[ Element 1 ] ---------\
[ Element 2 ] ----------+------------> [ Bucket 1 ]  (Count 1)
[ Element 3 ] ---------/
[ Element 4 ] -----------------------> [ Bucket 2 ]  (Count 2)

In the most extreme case, we can project the entire domain down to a single bit. In Inference under Information Constraints III: Local Privacy Constraints, Jayadev Acharya et al. introduce a mechanism called randomized one-bit isometry. By using a shared random seed, the domain is split into two halves. If two distributions are distinct in the original high-dimensional space, their 1-bit projections will maintain a proportional statistical distance. By repeating this test across multiple users with different random splits, a central observer can reconstruct the distance between the original distributions without ever seeing the high-dimensional data.


Bypassing the Privacy Noise Explosion

Domain compression is uniquely suited for privacy-preserving data collection. In Local Differential Privacy (LDP), users perturb their data before sending it to an untrusted server. If a protocol requires reporting a choice out of $k$ categories, the noise injected to achieve privacy scales heavily with $k$, rapidly destroying utility.

By hashing the domain down to a smaller virtual space before adding noise, the error margin is decoupled from the original domain size:

  • Optimal Distribution Testing: In Test without Trust: Optimal Locally Private Distribution Testing, Jayadev Acharya et al. demonstrate that standard private-coin mechanisms are sub-optimal for uniformity testing. They introduce RAPTOR, a mechanism that leverages public randomness to project the domain into a binary space. This converts a complex categorical test into a 1-bit bias estimation problem, reducing the required sample complexity from $O(k^{1.5})$ to the theoretical limit of $O(k)$.
  • Longitudinal Tracking: When monitoring data that changes over time, privacy budgets deplete quickly. Héber H. Arcolezi et al. propose the LOLOHA protocol in Frequency Estimation of Evolving Data Under Local Differential Privacy. By mapping values into a smaller virtual domain via hashing, they show that the cumulative privacy loss scales with the size of the hash range rather than the original domain, making long-term monitoring sustainable.
  • Heavy-Hitter Detection: Finding the most frequent items in a dataset of long strings typically incurs massive communication and privacy overhead. In Hash-Prune-Invert: Improved Differentially Private Heavy-Hitter Detection in the Two-Server Model, Albert Cheu et al. map high-dimensional data into a fixed-size hash space. This ensures that the privacy-preserving noise scales with the number of participants rather than the bit-length of the items, allowing popular items to be recovered efficiently via subsequent inversion.

This principle extends across intermediate privacy models as well. For instance, Badih Ghazi et al. demonstrate in Anonymized Histograms in Intermediate Privacy Models that random hashing into a number of buckets proportional to the sample size prevents error rates from exploding when the category count is much larger than the number of observed data points. Similarly, Albert Cheu et al. utilize domain hashing in Connecting Robust Shuffle Privacy and Pan-Privacy to reduce sample complexity bounds, while Ke Yi et al. leverage universal hash families in Frequency Estimation in the Shuffle Model with Almost a Single Message to minimize the number of messages each user must send.


The Power of Shared Randomness

The success of domain compression hinges on how the compression mapping is chosen. If Alice and Bob compress their data using completely independent random hash functions, the structural relationship between their datasets is lost.

To maintain statistical utility, protocols rely on shared randomness (or public coins). In Inference under Information Constraints II: Communication Constraints and Shared Randomness, Jayadev Acharya et al. show that when distributed users share a random seed to partition the domain, they can preserve the $\ell_2$ distance between their underlying distributions. This allows a central server to run chi-squared based uniformity tests on the compressed data. The authors prove that shared randomness provides a significant efficiency boost for identity testing, outperforming private-coin protocols by a factor of up to $\sqrt{k/2^\ell}$, where $\ell$ is the bit limit.

This trade-off is further formalized by Jayadev Acharya et al. in Communication-Constrained Inference and the Role of Shared Randomness, establishing that compressing the alphabet into buckets preserves sufficient chi-squared distance to distinguish distributions with high probability. It also serves as a core mechanism in Private Distribution Testing with Heterogeneous Constraints: Your Epsilon Might Not Be Mine, where Clement Louis Canonne et al. use public-coin domain compression to handle datasets with varying, heterogeneous privacy constraints.


Streamlining Memory and Two-Party Constraints

Beyond privacy and communication, domain compression serves as a fundamental algorithmic tool for saving memory in streaming environments and multi-party computation.

In memory-constrained streaming, storing a full histogram of a data stream is unfeasible. In Simpler Distribution Testing with Little Memory, Clement Louis Canonne et al. show that randomized hashing can be used as a general primitive for distribution testing. By compressing the incoming stream's domain, standard testing algorithms (like uniformity and closeness testing) can operate directly on the compressed counts within strict memory limits.

Data Stream:  X, Y, X, Z, W, X, Y...
                 |
                 v (Random Hash Function)
Hash Buckets: [ Bucket 1: 4 ]  [ Bucket 2: 3 ]
                 |
                 v
       Standard Statistical Test (Runs in O(1) Memory)

This strategy is also highly effective in adversarial streaming settings. Anders Aamand et al. demonstrate in Skirting Additive Error Barriers for Private Turnstile Streams that mapping high-dimensional item universes to smaller domains via random hashing allows for the private tracking of distinct elements and $F_2$ moments in turnstile streams, bypassing polynomial additive error barriers.

Finally, the same principle simplifies multi-party distribution problems. In Two Party Distribution Testing: Communication and Security, Alexandr Andoni et al. study a scenario where two parties hold separate sample sets and must test if their distributions are independent. By sampling a random subset of the alphabet to create a smaller sub-problem, they show that the communication overhead drops significantly, transforming a massive joint independence test into a manageable closeness test on a compressed sub-domain.

Whether defending against adversarial data manipulation—as explored by Jayadev Acharya et al. in Robust Testing and Estimation under Manipulation Attacks to maintain $\ell_1/\ell_1$ isometry—or minimizing local privacy budgets, the underlying conclusion remains the same: when dealing with high-dimensional discrete data, compressing the domain via shared randomness preserves the geometry of the distributions, allowing us to trade massive problem spaces for compact, resource-compliant representations.

Key Foundational Work

Inference under Information Constraints II: Communication Constraints and Shared Randomness (2019) — contributed 1 concept elements to this direction.
Communication-Constrained Inference and the Role of Shared Randomness (2019) — contributed 1 concept elements to this direction.
Test without Trust: Optimal Locally Private Distribution Testing (2019) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_domain_compression_90aaed77,
  title = {domain compression},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/domain-compression/rdr_90aaed771ef24f45892969a73b7b787a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_domain_compression_90aaed77_v1,
  title = {domain compression},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/domain-compression/rdr_90aaed771ef24f45892969a73b7b787a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake