Distinct Elements & Set Cardinality

Counting Names Without Keeping the Guest List

A venue may record ten ticket scans but only six different visitors. If someone scans the same ticket repeatedly, the event count grows while the number of distinct ticket IDs does not. An exact distinct count would keep a set of every ID. A cardinality sketch instead keeps a compact trace of hashed IDs and estimates how many different IDs could have produced it. This target is often called $F_0$, the number of nonzero coordinates in an insert-only frequency vector.

Start with scans A, B, A, C, B, D. There are six scans and four distinct IDs: $\{A,B,C,D\}$. Imagine assigning each distinct ID a reproducible random rank in $(0,1)$, such as A: $0.12$, B: $0.68$, C: $0.42$, D: $0.31$. Repeated A has the same rank, so it cannot change the minimum. A small minimum suggests that many different IDs had chances to produce a rare low rank; it is evidence, not an exact conversion to four. Another approach notices unusually long runs of zero bits in hashes. Both approaches turn rare hash patterns into evidence about a set's size.

The key is the identity contract. Counting unique users, devices, or transactions requires stable canonical IDs for the intended entity. Repeated events should hash to the same value, and different workers must agree on encoding and hash seed to merge summaries. The previous chapters' hash assumptions and concentration tools tell us why one register is noisy, why aggregation helps, and where the guarantee ends.

From Occupancy to Leading-Zero Statistics

Fix a set $S$ of $n$ distinct keys and a stable hash function. In a mathematical idealization, each distinct key receives an independent uniform hash value; repeats reuse that value. For a uniform binary hash, the probability that a value ends in at least $r$ zero bits is $2^{-r}$, as long as the hash has enough bits. Among about $n$ distinct values, seeing a run near $\log_2n$ is plausible. The Flajolet–Martin idea records the largest trailing-zero run or related bitmap evidence. Turning that statistic into an estimate requires calibration and variance control; $2^R$ alone is not an unbiased general estimator. Leading-zero conventions express the same rarity when bit order is chosen consistently.

Another view uses hash order statistics. Give each distinct key an independent continuous uniform rank in $(0,1)$ and sort the ranks. For $1\le k\le n$, the $k$th smallest rank $R_k$ has $\mathbb E[R_k]=k/(n+1)$. For $k>1$, $\mathbb E[1/R_k]=n/(k-1)$, so $(k-1)/R_k$ is unbiased for $n$ under this ideal model. One sample can still be far from $n$, and the reciprocal of the single minimum has infinite mean in this continuous idealization. Real finite-width hashes also have ties and a limited range; the ideal equations are not automatically exact for a deployed implementation.

Stochastic averaging splits keys among several registers using hash-prefix bits, reducing reliance on a single extreme run. LogLog-type schemes aggregate register values with calibrated constants; HyperLogLog (HLL) uses a harmonic-style aggregation of powers of the register values. If $m$ is a power of two, the first $\log_2m$ hash bits select register $j$, and the suffix contributes $\rho$, the position of its first $1$ bit, starting at $1$. Update $M_j\leftarrow\max(M_j,\rho)$. A common raw estimate has form $E_{\mathrm{raw}}=\alpha_m m^2/(\sum_{j=1}^{m}2^{-M_j})$, with a calibration factor $\alpha_m$. Practical implementations need corrections, especially when cardinality is small relative to $m$ or approaches the finite hash range.

At small cardinalities, linear counting uses the number $V$ of empty registers or buckets: $\widehat n\approx m\ln(m/V)$ when $V>0$, under a suitable uniform occupancy model. The familiar HLL small-range correction uses this idea when many registers are still zero; the exact switch and bias correction belong to an implementation's documented estimator. When $V=0$, the formula cannot be used. None of these insert-only summaries directly supports removing an arbitrary key that may still occur elsewhere.

flowchart TD
    S["Stable hash per distinct key"] --> R{"Retained statistic"}
    R -->|Small ranks| O["Order statistics"]
    R -->|Rare zero runs| F["Flajolet-Martin idea"]
    F --> A["Partition into registers"]
    A --> L["LogLog or HLL aggregation"]
    A --> V["Empty-register occupancy"]
    V --> C["Linear-counting correction"]
    O --> E["Estimated F0"]
    L --> E
    C --> E
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class S,R navy; class O,F,A,L,E teal; class V,C purple;

Bias, Variance and Register Aggregation

Rare patterns provide a scale but not a ready-made accuracy guarantee. For uniform independent hashes, $\Pr(R_1>u)=(1-u)^n$: all $n$ ranks must exceed $u$. A very small observed minimum is possible even for a small set. Using $1/R_1$ as if it were a reliable count fails sharply: for continuous ranks its expected value diverges. Keeping the $k$th smallest rank with $k>1$ avoids that particular pathology. The estimator $(k-1)/R_k$ is unbiased for $n$ under the ideal model, yet its variance is finite only when $k>2$; for $k>2$, $\operatorname{Var}((k-1)/R_k)=n(n-k+1)/(k-2)$. This follows from the beta distribution of $R_k$ and its reciprocal moments, not from merely replacing a random denominator by its mean.

For HLL, multiple registers spread keys across partitions and the harmonic-style denominator dampens the influence of one unusually large register. Under an appropriate ideal hash model and sufficiently large cardinality, the familiar asymptotic relative standard error is about $1.04/\sqrt m$ for the classical estimator; this is a rule of thumb for its operating regime, not a universal guarantee at tiny $n$, hash saturation, or adversarial inputs. An estimate also has bias, especially at range boundaries; empirical corrections and an empty-register regime matter. A confidence statement needs an actual error analysis or measured calibration, not only an RSE number.

Union estimation has a clean state rule. If sketches A and B share the same hash function, register count, encoding, and register definitions, then for each $j$, $M_j(A\cup B)=\max(M_j(A),M_j(B))$. Proof: the maximum over all keys in a union is the maximum of the two local maxima. Duplicate keys yield identical hash outcomes and do not add new evidence. The cardinality estimate is computed after the coordinatewise merge; adding the two scalar estimates double-counts overlap and is not the HLL union operation. The same maximum cannot undo a deletion or remove one day from a combined sketch, since it does not record which contributing key supplied a maximum.

flowchart TD
    H["Stable uniform hash per key"] --> R["Rare rank or zero-run observation"]
    R --> S{"How much state?"}
    S -->|One minimum| V["High or infinite reciprocal variance"]
    S -->|kth smallest, k > 2| O["Unbiased inverse-rank estimate"]
    S -->|Many registers| M["HLL calibrated aggregation"]
    M --> U["Compatible union: max per register"]
    O --> E["Analyze bias, variance, and range"]
    M --> E
    U --> E
    V --> E
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class H,R navy; class O,M,U,E teal; class V crimson; class S purple;

Daily Users, Devices and Distributed Unions

Approachable daily visitors. A small museum records IDs on Monday A, B, C, A and Tuesday B, D, E. Monday has three distinct IDs, Tuesday has three, and their union has five, not six. Counting individual scans would give seven. A shared-hash cardinality sketch can merge compatible daily states by register maxima to estimate the union; it cannot subtract Monday's contribution later to recover Tuesday unless Tuesday's own sketch was retained.

Production analytics. Consider daily active user estimates from four regions, each processing millions of events. The specification must define the user ID, what “day” means in each region, how late events are assigned, and whether opt-outs or deleted accounts are excluded. All workers need identical hash version, seed, register count, and encoding. Their register arrays can be merged for a global daily union. If the target requires a 2% relative standard error in the classical large-range approximation, $m$ around $(1.04/0.02)^2=2{,}704$ suggests choosing a supported power of two such as $4{,}096$ registers. The actual memory includes register width and metadata; a confidence or service-level promise needs testing across realistic cardinalities, including small groups and hash-range boundaries.

Misleading or adversarial case. Device IDs rotate for privacy, causing one physical device to look like several distinct keys. Conversely, two people sharing one account ID look like one user. Neither is “fixed” by increasing registers. If an adversary can choose identifiers after learning the hash seed, it may seek values that distort register patterns; fixed-key random-hash analyses do not cover that choice. Small groups can also yield unstable estimates or privacy concerns, so an exact threshold decision may require an authoritative count or a separate policy. These are target-definition and threat-model questions before they are estimator questions.

Plan a Cardinality Study

Pick the entity and time scope before the sketch. Then decide which ideal hash model the estimator's reasoning uses, how much state is available, and whether the answer must be mergeable, retractable, or exact near a decision threshold. The exercises make the distinction between mathematical sketch error and inconsistent IDs visible.