Frequency Estimation of Visited Cells with LDP

Once the domain grows past a few dozen cells, direct randomised response stops being usable and the question becomes which estimator recovers per-cell frequencies with the least variance for a given ε\varepsilon and a given upload budget. This page implements and compares the two workhorses — optimised unary encoding and local hashing — and derives the error bars that must accompany any published estimate. It sits under local differential privacy for mobile clients in Differential Privacy for Geospatial Data, and the estimates it produces are consumed by the same benchmarks used for privatized heatmaps.

Parameter Configuration and Calibration

  • Mechanism choice by domain size. Optimised unary encoding (OUE) has per-client variance 4eε/(eε−1)24e^{\varepsilon}/(e^{\varepsilon}-1)^2, independent of the domain — excellent, at the cost of dd bits per upload. Optimal local hashing (OLH) hashes into g=⌈eε+1⌉g = \lceil e^{\varepsilon}+1 \rceil buckets and uploads a single small integer, with variance close to OUE’s. Rule of thumb: OUE below a few thousand cells, OLH above.
  • epsilon per distinct value. Variance falls roughly as e−εe^{-\varepsilon} at small ε\varepsilon, so moving from 1 to 2 is a large win and from 4 to 5 is not. Most deployments live between 1 and 3.
  • min_reporters — the publication floor. Both mechanisms have variance proportional to nn, so the standard error of a count grows as n\sqrt{n} while a cell’s true count grows as nn. Compute the floor from the smallest count you need to distinguish, not from a round number.
  • hash_seed_source for OLH. Each client draws its own hash seed and uploads it with the report; the server groups by seed when aggregating. A shared seed collapses the estimator and, worse, makes two clients with the same true cell indistinguishable from a collision — which the estimator cannot correct for.
Mechanism Upload per report Per-client variance Best for
Direct randomised response 1 cell id grows with dd d≲50d \lesssim 50
Optimised unary encoding dd bits 4eε/(eε−1)24e^{\varepsilon}/(e^{\varepsilon}-1)^2 d≲3,000d \lesssim 3{,}000
Optimal local hashing seed + small int ≈\approx OUE + a small penalty large dd
Per-client variance for three mechanisms A grouped bar chart of per-client estimator variance for three local-differential-privacy mechanisms at four budgets. Unary encoding and local hashing are close throughout, with hashing paying a small collision penalty. Direct randomised response at a 64-cell domain is substantially worse at every budget, and the gap widens as epsilon falls. Per-client variance for three mechanisms lower is better; direct RR is shown at a 64-cell domain 0 50 100 150 variance per client 15.7 16.9 155.2 ε = 0.5 3.7 4.0 22.9 ε = 1.0 0.7 0.8 1.9 ε = 2.0 0.1 0.1 0.1 ε = 4.0 unary encoding local hashing direct RR (d = 64)
Hashing costs about 8% more variance than unary encoding and uploads a few bytes instead of a bit per cell — which is why it wins everywhere the grid is large.

Reference Implementation

python
from __future__ import annotations

import hashlib
import math
import secrets
from dataclasses import dataclass
from typing import Sequence

import numpy as np


@dataclass(frozen=True)
class OLHParams:
    """Optimal local hashing: hash into g buckets, then randomise the bucket."""

    epsilon: float
    domain: int

    @property
    def g(self) -> int:
        """Bucket count that minimises estimator variance."""
        return max(2, int(round(math.exp(self.epsilon))) + 1)

    @property
    def p(self) -> float:
        e = math.exp(self.epsilon)
        return e / (e + self.g - 1)

    @property
    def q(self) -> float:
        return 1.0 / (math.exp(self.epsilon) + self.g - 1)

    def variance_per_client(self) -> float:
        p, q = self.p, self.q
        # 1/g is the collision probability an unrelated cell has with the report.
        return (q * (1 - q)) / ((p - q) ** 2)


def _bucket(cell: int, seed: int, g: int) -> int:
    """Deterministic hash of a cell into one of g buckets, under a client seed."""
    digest = hashlib.blake2b(f"{seed}:{cell}".encode(), digest_size=8).digest()
    return int.from_bytes(digest, "big") % g


def olh_report(true_cell: int, params: OLHParams) -> tuple[int, int]:
    """Produce one (seed, perturbed bucket) report on the device."""
    if not 0 <= true_cell < params.domain:
        raise ValueError("cell outside the declared domain")
    seed = secrets.randbits(32)
    true_bucket = _bucket(true_cell, seed, params.g)
    if secrets.randbelow(10 ** 9) < int(params.p * 10 ** 9):
        return seed, true_bucket
    other = secrets.randbelow(params.g - 1)
    return seed, other if other < true_bucket else other + 1


def olh_estimate(reports: Sequence[tuple[int, int]], params: OLHParams) -> np.ndarray:
    """Recover unbiased per-cell counts from hashed, perturbed reports.

    A report "supports" cell c when the client's own hash maps c to the reported
    bucket. Every cell therefore collects support from unrelated clients at rate
    1/g, and the inversion below removes exactly that floor.
    """
    n = len(reports)
    support = np.zeros(params.domain)
    for seed, bucket in reports:
        for cell in range(params.domain):
            if _bucket(cell, seed, params.g) == bucket:
                support[cell] += 1.0
    p, q = params.p, params.q
    return (support - n * q) / (p - q)


def standard_error(n: int, params: OLHParams) -> float:
    return math.sqrt(n * params.variance_per_client())


def publishable(estimate: float, n: int, params: OLHParams, z: float = 1.96) -> bool:
    """A cell is publishable only when its estimate clears its own error bar."""
    return estimate > z * standard_error(n, params)

Validation Checkpoint

python
def _validate() -> None:
    rng = np.random.default_rng(41)
    params = OLHParams(epsilon=2.0, domain=64)

    truth = np.concatenate([
        np.full(30_000, 7), np.full(18_000, 22),
        rng.integers(0, 64, size=52_000),
    ])
    reports = [olh_report(int(c), params) for c in truth]
    est = olh_estimate(reports, params)
    true_counts = np.bincount(truth, minlength=64).astype(float)
    se = standard_error(truth.size, params)

    # 1. The two planted hotspots must be recovered within a few standard errors.
    for cell in (7, 22):
        assert abs(est[cell] - true_counts[cell]) < 4 * se, (cell, est[cell], true_counts[cell])

    # 2. The estimator is unbiased overall, not just on the peaks.
    assert abs(float(np.mean(est - true_counts))) < se

    # 3. The bucket count must follow the closed form, or the variance is wrong.
    assert params.g == max(2, round(math.exp(2.0)) + 1)

    # 4. A cell whose estimate is inside its error bar must not be publishable.
    quiet = int(np.argmin(true_counts))
    assert not publishable(est[quiet], truth.size, params)

    # 5. More budget must reduce the standard error.
    tighter = OLHParams(epsilon=4.0, domain=64)
    assert standard_error(truth.size, tighter) < se

    # 6. Every client must use its own seed — a shared seed breaks the estimator.
    seeds = {s for s, _ in reports}
    assert len(seeds) > 0.9 * len(reports), "client seeds must be independent"

    print("LDP frequency estimation: all assertions passed")


_validate()
The smallest count that is publishable at all Two curves against the reporting population on a logarithmic axis. The absolute ninety-five percent error bar grows as the square root of the population, from about 80 counts at a thousand clients to about 2,500 at a million. Expressed as a share of the population it falls steeply, from eight percent to a quarter of a percent, which is the sense in which local differential privacy needs a crowd. The smallest count that is publishable at all ε = 2, unary encoding; a cell below its own bar is noise 1000 10000 100000 1000000 0 500 1000 1500 reporting clients n counts / % 95% error bar (counts) bar as % of the population
Any cell whose estimate is inside this bar must be suppressed. At a million reporters that still means every cell holding fewer than ~2,500 devices.

Assertion 4 encodes the discipline that separates a usable LDP release from a misleading one. Under LDP most cells in a fine grid are not publishable at any realistic population, and a pipeline that publishes them anyway is presenting sampling noise as geography.

Incident Response and Edge Cases

  • Server-side aggregation is too slow. OLH’s inversion tests every cell against every report’s hash, which is O(nd)O(nd). Precompute, per seed, the bucket assignment of every cell once, and group reports by seed — the seed space is small enough that this collapses to a handful of table lookups per report.
  • The estimates are stable but the ranking is wrong. Look at the error bars: with overlapping intervals, the ranking between two cells is not determined by the data. Publish ranks only where intervals are disjoint, or publish bands instead of ranks.
  • A hot cell’s estimate exceeds the total client count. Possible and legitimate for a single draw, since the estimator is unbiased rather than bounded. Do not clip; report the interval. If it happens routinely, the reporter count is too low for the chosen ε\varepsilon.
  • Two client versions use different bucket counts. Their reports cannot be pooled. Group by parameter version at aggregation time and combine only the final estimates, weighted by reporter count.
  • Estimates drift week over week with no real change. Check whether the reporting population is stable. LDP estimates are counts of reporters, not of people, and a change in app engagement moves every cell.
A fleet mid-rollout reports under two parameter sets A four-row table about aggregating reports during a client rollout. Single-version populations invert cleanly. A mixed population inverted with one version's parameters produces a large, silent bias and is unusable. Aggregating each version separately and combining the unbiased estimates afterwards restores correctness. A fleet mid-rollout reports under two parameter sets inverting a mixed tally with either version's parameters is silently wrong bias usable? v3 clients only none yes v4 clients only none yes mixed, inverted as v4 large, silent no mixed, per-version none yes
Transmit the parameter version with every report and group by it. The failure mode otherwise is a plausible, wrong map for the whole duration of a rollout.

One implementation detail is worth stating explicitly because it is a frequent source of silent error: the estimator’s parameters must be the ones the client used, not the ones currently configured on the server. Clients update on their own schedule, so a fleet mid-rollout is reporting under two parameter sets at once. Transmit the parameter version with every report, aggregate each version separately, and combine only the final unbiased estimates weighted by reporter count. Inverting a mixed-version tally with either version’s parameters produces a biased result that looks entirely plausible.

Frequently Asked Questions

Why does local hashing beat unary encoding for big grids?

Not on variance — the two are close — but on upload size. Unary encoding sends one bit per domain element, which is impractical once the grid has tens of thousands of cells. Hashing sends a seed and a small integer regardless of domain size, and pays only a modest variance penalty from collisions.

Do I need to publish error bars?

Yes. Under LDP the error bar is frequently larger than the counts in most cells, and a release without it invites consumers to read structure that is not there. The bar depends only on public parameters and the reporter count, so publishing it discloses nothing extra.

Can I aggregate over several epochs to reduce noise?

Only if each client's contribution across those epochs was memoised. Otherwise you are averaging independent randomisations of the same underlying value, which reduces noise precisely because it erodes the guarantee — the client has spent budget for each epoch.

How do I detect a hostile client population?

Poisoned reports look like a shifted frequency distribution, and LDP gives the server no way to validate an individual report. Defend statistically: cap each client's contribution, monitor the distribution of reported buckets for departures from the uniform floor the mechanism predicts, and treat sudden shifts in previously stable cells as an incident rather than as data.

Up one level: Local Differential Privacy for Mobile Clients · Section: Differential Privacy for Geospatial Data.