l0-Sampling in Dynamic Streams

Return One Nonzero Coordinate

Let a dynamic stream define a frequency vector \(x\in\mathbb Z^n\). Updates \((i,\Delta)\) add \(\Delta\) to coordinate \(x_i\); later updates may cancel earlier ones. The support is \[ \operatorname{supp}(x)=\{i:x_i\ne0\},\qquad \lVert x\rVert_0=|\operatorname{supp}(x)|. \] An \(L_0\)-sampler returns one index chosen uniformly from the final support, or reports EMPTY when the vector is zero, with a small allowed failure probability.

Imagine a warehouse board showing net inventory changes. A product added five times and removed five times is inactive even though it appeared in ten events. Sampling a random event would overrepresent busy products and might return one whose final coordinate is zero. An \(L_0\)-sampler instead chooses uniformly among currently nonzero product coordinates.

For a tiny vector \(x=(0,3,0,-2,5)\), the support is \(\{2,4,5\}\). Each of these indices should be returned with probability \(1/3\), regardless of whether its magnitude is \(3,-2,\) or \(5\). If updates \((4,+2)\) and \((2,-3)\) arrive, the vector becomes \((0,0,0,0,5)\), and the only valid answer is index \(5\).

This deep dive builds on linear sketches and sparse recovery. Support sampling concerns identities of nonzero coordinates, not their magnitudes. Subsampling levels retain each coordinate at geometrically decreasing probabilities. A one-sparse recovery certificate decides whether a level contains exactly one live coordinate and recovers it. Fingerprints are independent algebraic checks that make false decodes unlikely. Turnstile cancellation works because every stored measurement is linear in \(x\). A failure event includes no isolated level, a hash or fingerprint collision, arithmetic overflow, or violated stream assumptions.

The output is not a weighted sample. A coordinate of magnitude one and a coordinate of magnitude one million receive equal \(L_0\) probability. Uniformity and correctness are over internal randomness fixed independently of a nonadaptive stream; adaptive adversaries who learn seeds require a stronger threat model.

Isolation, Subsampling Levels and Recovery

Choose \(L=\lceil\log_2 n\rceil+1\) nested levels. A coordinate hash \(h(i)\) determines inclusion in level \(j\) with probability approximately \(2^{-j}\); nesting means inclusion in a sparse level implies inclusion in all denser levels. For support size \(s=\lVert x\rVert_0\), a level near \(j^\star=\lfloor\log_2 s\rfloor\) has expected sampled support \(\Theta(1)\). At that scale, the probability that exactly one coordinate survives is a positive constant: \[ \Pr[\text{one survivor}] =s p(1-p)^{s-1} \] for ideal independent inclusion probability \(p\) near \(1/s\). Repeating independent hierarchies drives the probability of no isolation down exponentially.

Each level stores linear measurements over a large prime field \(\mathbb F_p\). A readable one-sparse certificate uses \[ A=\sum_i x_i,\quad B=\sum_i i x_i,\quad C=\sum_i i^2x_i,\quad D=\sum_i g(i)x_i, \] where all sums are restricted to sampled coordinates and \(g\) is an independent fingerprint hash. If exactly one coordinate \(q\) with value \(v\) remains, then \[ A=v,\quad B=qv,\quad C=q^2v,\quad D=g(q)v. \] When \(A\ne0\), recover \(q=B/A\) in the field and verify \(C=qB\) and \(D=g(q)A\). Also verify that \(q\) lies in the declared universe and was eligible for that level. A multi-sparse state can occasionally satisfy algebraic equalities by collision, but an independent fingerprint over a large field makes false acceptance unlikely.

Linearity gives dynamic updates. Update \((i,\Delta)\) adds \(\Delta,\ i\Delta,\ i^2\Delta,\ g(i)\Delta\) to every level containing \(i\). A later \((i,-\Delta)\) subtracts exactly the same quantities. Sketches with identical parameters, fields, hashes, and level definitions merge by componentwise addition.

Uniformity comes from symmetry: every final support coordinate is treated identically by the random hierarchy. Conditioned on a valid isolated recovery, each coordinate has the same chance of being the isolated survivor. A complete construction coordinates level choice, repetitions, and deduplication so the returned index remains uniform, while failure is reported separately.

Boundary cases matter. If two live coordinates have values that sum to zero, then \(A=0\) even though the level is nonempty; the decoder must not declare EMPTY solely from one level. If the modulus is too small, a nonzero frequency can become zero modulo \(p\). If inclusion is chosen per update rather than per coordinate, deletions do not cancel. An exact support map with a random priority is a useful oracle but uses support-sized memory and is not an \(L_0\)-sketch.

flowchart TD
    A[Dynamic coordinate updates] --> B[Stable nested hash levels]
    B --> C[Level inclusion probability halves geometrically]
    C --> D[Some level has expected support near one]
    D --> E[Constant chance of exactly one survivor]
    E --> F[Linear moments A B C and fingerprint D]
    F --> G{One-sparse equations verify?}
    G -->|yes| H[Recover coordinate and value]
    G -->|no| I[Reject this level]
    H --> J[Symmetric randomness gives uniform support sample]
    I --> K[Try another level or repetition]
    J --> L[Repeat to reduce failure]
    B --> M{Hash changes per update or seed exposed?}
    M -->|yes| N[Cancellation or adversary model fails]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,C,D navy;
    class E,F,K,L purple;
    class G,H,J teal;
    class I,M,N crimson;

Dynamic Updates and Failure Probability

Let support size be \(s\). At a level with \(p\in[1/(2s),1/s]\), ideal independent sampling gives \[ sp(1-p)^{s-1} \] probability of exactly one survivor, which is bounded below by a positive constant. If one hierarchy succeeds with probability at least \(c\), then \(r\) independent repetitions all fail with probability at most \((1-c)^r\). Thus \(r=O(\log(1/\delta))\) repetitions suffice for isolation failure at most \(\delta\). Fingerprint collisions consume another error budget, commonly bounded by \(O(1/p_{\text{field}})\) per attempted decode and union-bounded across levels and repetitions.

The randomness requirements depend on the proof. Pairwise-independent level hashing may control some isolation calculations; stronger independence or carefully designed hash families may be used for uniformity and adversarial robustness. Fingerprints must be independent of the moments they certify. Production documentation should state the family, seed lifecycle, field modulus, number of levels, repetitions, and final union-bound budget.

Consider \(x_2=3,x_5=-2,x_7=4\). Suppose a level includes only coordinate \(5\). Then \(A=-2\), \(B=-10\), \(C=-50\), and \(D=-2g(5)\) over the field. Dividing \(B/A\) recovers \(5\), and both checks pass. If update \((5,+2)\) arrives, every measurement contribution for coordinate \(5\) becomes zero; the level is empty rather than still remembering its history.

Perturb the level so it contains coordinates \(2\) and \(5\). Then \(A=1,B=-4,C=-38\). The candidate \(q=B/A=-4\) is outside the universe, so decoding rejects immediately. Other multi-sparse combinations may produce an in-range ratio, which is why the second moment and fingerprint are both checked.

Arithmetic is a real boundary. Frequencies must not wrap before modular reduction, the prime must exceed the coordinate encoding requirements, and division needs \(A\ne0\). A true nonzero coordinate divisible by the field prime is invisible modulo that field; bounded-frequency assumptions or multiple moduli address this.

from hashlib import blake2b

PRIME = 2_305_843_009_213_693_951

def h64(seed, domain, value):
    raw = f"{seed}|{domain}|{value}".encode()
    return int.from_bytes(blake2b(raw, digest_size=8, person=b"l0-demo-v1").digest(), "big")

def inv(value):
    return pow(value % PRIME, PRIME - 2, PRIME)

class LinearL0Sampler:
    def __init__(self, universe, repetitions=12, seed=5):
        if universe < 1 or repetitions < 1:
            raise ValueError("positive universe and repetitions required")
        self.universe = universe
        self.repetitions = repetitions
        self.level_count = universe.bit_length() + 1
        self.seed = seed
        self.cells = [[[0, 0, 0, 0] for _ in range(self.level_count)]
                      for _ in range(repetitions)]

    def _priority(self, rep, index):
        return h64(self.seed + rep, "level", index)

    def _fingerprint(self, rep, index):
        return h64(self.seed + rep, "finger", index) % PRIME

    def _included(self, rep, level, index):
        threshold = 1 << max(0, 64 - level)
        return self._priority(rep, index) < threshold

    def update(self, index, delta):
        if not 1 <= index <= self.universe or not isinstance(delta, int):
            raise ValueError("valid coordinate and integer delta required")
        for rep in range(self.repetitions):
            for level in range(self.level_count):
                if not self._included(rep, level, index):
                    continue
                cell = self.cells[rep][level]
                cell[0] = (cell[0] + delta) % PRIME
                cell[1] = (cell[1] + index * delta) % PRIME
                cell[2] = (cell[2] + index * index * delta) % PRIME
                cell[3] = (cell[3] + self._fingerprint(rep, index) * delta) % PRIME

    def _decode(self, rep, level):
        a, b, c, d = self.cells[rep][level]
        if a == 0:
            return None
        q = b * inv(a) % PRIME
        if not 1 <= q <= self.universe:
            return None
        if c != q * b % PRIME:
            return None
        if d != self._fingerprint(rep, q) * a % PRIME:
            return None
        if not self._included(rep, level, q):
            return None
        value = a if a <= PRIME // 2 else a - PRIME
        return int(q), value

    def sample(self):
        candidates = []
        for rep in range(self.repetitions):
            for level in range(self.level_count - 1, -1, -1):
                decoded = self._decode(rep, level)
                if decoded is not None:
                    candidates.append((self._priority(rep, decoded[0]), decoded))
                    break
        return None if not candidates else min(candidates)[1]

updates = [(2, 5), (4, -3), (7, 9), (2, -2), (7, -9), (9, 4)]
sampler = LinearL0Sampler(32, repetitions=20, seed=11)
exact = {}
for index, delta in updates:
    sampler.update(index, delta)
    exact[index] = exact.get(index, 0) + delta
support = {i for i, value in exact.items() if value != 0}
sample = sampler.sample()
assert sample is not None and sample[0] in support and sample[1] == exact[sample[0]]

empty = LinearL0Sampler(16, repetitions=8)
empty.update(3, 7)
empty.update(3, -7)
assert empty.sample() is None

bad = LinearL0Sampler(8, repetitions=1)
bad.cells[0][0] = [1, 2, 99, 7]
assert bad._decode(0, 0) is None

try:
    sampler.update(0, 1)
    raise AssertionError("invalid coordinate accepted")
except ValueError:
    pass

print("support:", sorted(support), "sample:", sample)
print("empty:", empty.sample(), "false certificate:", bad._decode(0, 0))

Sampling Active Keys After Deletions

In a teaching case, maintain a small exact vector alongside the linear measurements. Apply additions and deletions, recompute support, and verify that every decoded pair belongs to the final support. Enumerate hash choices on a tiny universe to observe isolation and failure separately.

In dynamic graph streaming, coordinates can represent edges. Insertions add edges and deletions remove them; an \(L_0\)-sampler can return a surviving edge from a cut or incidence-defined vector without listing all edges. This becomes a primitive in spanning-forest and connectivity algorithms. The coordinate encoding must be canonical so the same undirected edge cancels under deletion.

In a security or telemetry system, coordinates may be active alert keys. Uniform support sampling can audit rare and common active keys equally, unlike event sampling. It is appropriate only if the final signed counts define meaningful activity and field/counter ranges cover all possible values.

Failure and adversarial cases include clients learning seeds and crafting collisions, noncanonical key encodings, deleting nonexistent items when a strict-turnstile interpretation was assumed, field wraparound, and using one seed for level selection and certification. Evidence invalidating deployment includes decoded zero coordinates, empirical sample frequencies outside statistical tolerance, false certificates against exact audits, excessive FAIL rate, or merge headers that disagree on field, universe, seeds, or repetitions.

flowchart TD
    A[Define final support and uniformity target] --> B{Insertions and deletions?}
    B -->|yes| C[Evaluate linear L0 sampler]
    B -->|no| D[Compare reservoir or simpler methods]
    C --> E[Choose universe field levels repeats and hashes]
    E --> F[Fix canonical coordinate encoding]
    F --> G[Validate against exact dynamic support]
    G --> H{Validity uniformity and failure acceptable?}
    H -->|no| I[Reject strengthen or resize]
    H -->|yes| J[Version seeds and deploy]
    J --> K[Monitor FAIL false decode and field range]
    K --> L{Adversary and assumptions unchanged?}
    L -->|yes| K
    L -->|no| I
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,F navy;
    class C,E purple;
    class G,J,K teal;
    class D,H,I,L crimson;

Build an l0-Sampler Certificate

Mastery begins by separating three claims: a coordinate is isolated, its index/value are algebraically recoverable, and the overall output distribution is uniform over final support. Write a proof obligation for each. Derive the one-survivor probability near \(p=1/s\), then amplify failure across independent repetitions and union-bound fingerprint collisions.

Implementation traces should record the final exact vector, coordinate priorities, level inclusions, field moments, candidate division, moment check, fingerprint check, and final outcome. Debug per-update randomness, a shared fingerprint/level hash, too-small modulus, missing universe check, signed-to-field conversion, and seed mismatches during merge.

For extension, derive \(L_1\)-sampling and compare its magnitude-weighted objective, recover several support coordinates, or embed \(L_0\)-samplers in dynamic graph connectivity. This bridges one-sparse recovery to sparse recovery, support-size estimation, and distributed linear sketches.