Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces two fast simulation algorithms for Optimized Local Hashing (OLH) that leverage Binomial modeling to significantly reduce computational complexity from \(O(nd)\) to \(O(n + d)\). By decomposing the total number of users whose perturbed reports support a domain value into Binomial random variables, the authors ensure that statistical equivalence is maintained while achieving unbiased frequency estimations. Experimental results demonstrate that these algorithms can reduce execution times from several minutes to milliseconds without compromising utility, making them highly efficient for OLH applications.
Achieving simulation speedups from minutes to milliseconds, our new algorithms maintain statistical integrity while slashing computational complexity for OLH applications.
Optimized Local Hashing (OLH) is a widely used hash-based Local Differential Privacy (LDP) protocol, and simulation-based experimentation is the standard approach for evaluating OLH and OLH-based applications in research. However, the existing OLH simulations have $O(nd)$ computational complexity, where $n$ is the user population size and $d$ is the domain size, and can lead to significant execution times as $n$ and $d$ grow. In this paper, we propose two fast simulation algorithms for OLH (2-Binom and 3-Binom) grounded in Binomial modeling. Our key insight is that, for any domain value $v$, the total number of users whose perturbed reports support $v$ can be decomposed into a sum of two or three Binomial random variables. Using this insight, our algorithms reduce the simulation complexity to $O(n + d)$ without hurting statistical equivalence. In particular, we theoretically prove that both algorithms yield unbiased frequency estimations with variances identical to those of the original OLH simulations. Experiments on real-world datasets confirm that both approaches reduce execution times from several minutes to milliseconds, yielding significant speedups with no change in utility.