Evaluation, Testing & Algorithm Selection

The Best Sketch Depends on the Question

There is no universally best sketch. A compact cardinality estimator may excel at distinct users but cannot answer quantiles; a frequency sketch may estimate point counts but not preserve geometric clustering cost. Even two algorithms for the same statistic can trade memory, update latency, merge cost, tail error, serialization size, and resilience differently.

The familiar analogy is choosing transport. “Fastest vehicle” is incomplete without distance, cargo, roads, cost, and reliability. Likewise, “$O(1)$ update” hides constants, cache misses, vectorization, concurrency, and parameter-dependent state. Selection starts with the decision and workload, then tests candidates under the same inputs, budgets, and success criteria.

Suppose candidate A uses $8$ MB, processes $5$ million updates per second, and has p99 relative error $1.5\%$. Candidate B uses $2$ MB, processes $8$ million updates per second, and has p99 error $4\%$. If the error SLO is $2\%$, B is infeasible despite winning memory and throughput. If the SLO is $5\%$ on constrained edge devices, B may dominate.

Evidence must include ordinary and hostile conditions: skew, rare keys, changing cardinality, burstiness, deletions, merge trees, retries, saturation, incompatible states, and adaptive or malformed inputs where relevant. A benchmark is an argument about a defined population—not a property of the algorithm in every environment.

Workloads, Oracles and Evaluation Metrics

An evaluation instance consists of workload $W$, candidate $A_\theta$ with parameter vector $\theta$, resource environment $E$, exact oracle $g$, and metric family $M$. Repeated trials vary input samples, algorithm seeds, machine noise, or all three—but the report must say which variation each interval represents.

For truth $y_i$ and estimate $\widehat y_i$, absolute error is $\lvert\widehat y_i-y_i\rvert$. Relative error is undefined at $y_i=0$ unless a policy is declared. Symmetric, normalized, rank, set-recall, or objective-specific loss may be better. Averages can hide tails and subgroups, so report quantiles, worst supported cases, failure rate, signed bias, and slices relevant to the decision.

Accuracy probability requires calibration. If a construction claims failure at most $\delta$, run independent trials under its theorem’s model, define failure before observing results, and estimate the rate with a confidence interval. Passing $100$ trials cannot establish a one-in-a-million guarantee.

Performance measurement separates warm-up, steady state, allocation, serialization, update, query, and merge. Report hardware, runtime, compiler, concurrency, batch size, state occupancy, memory accounting, and backpressure. Resident memory is not the same as payload bytes.

Ground truth may be computed exactly on smaller windows, sampled streams, or replayable partitions. Validate the oracle against independent implementations and include duplicate, window, weighting, and deletion semantics.

flowchart TD
    A[Decision and SLOs] --> B[Formal workload model W]
    A --> C[Exact oracle semantics]
    A --> D[Metric definitions]
    B --> E[Representative corpus]
    B --> F[Stress and adversarial corpus]
    C --> G[Ground-truth outputs]
    D --> H[Pre-registered success criteria]
    E --> I[Common trial harness]
    F --> I
    G --> I
    H --> I
    I --> J[Accuracy confidence performance resources]
    J --> K[Feasibility gates]
    K --> L[Pareto and risk decision]
    C --> X[Failure if oracle semantics differ]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    class A,B,C,D navy;
    class E,F,G,H,I purple;
    class J,K,L teal;
    class X crimson;

Crossover Points, Coverage and Failure Injection

Candidate rankings often change with scale. An exact map may beat a sketch for small cardinalities because allocation and hashing constants dominate; the sketch wins after exact memory/cache costs rise. Find crossover points with parameter sweeps rather than one “large” benchmark.

Suppose measured memory is $M_E(n)=32n$ bytes for an exact map and $M_S=1{,}048{,}576$ bytes for a fixed sketch. The memory crossover solves $32n=M_S$, giving $n=32{,}768$. This says nothing about accuracy or latency, and real maps have nonlinear/cache effects, so empirical sweeps must verify the model.

Coverage studies combine dimensions: cardinality, skew, update/query mix, batch size, merge fan-in/depth, deletions, key encoding, thread count, and hardware. Full Cartesian grids may be too expensive; use designed sweeps, boundary values, risk-based pairwise combinations, and targeted adversarial cases.

Failure injection asks whether operational assumptions hold: replay batches, drop partitions, corrupt lengths/checksums, mix versions or seeds, saturate counters, force hash collisions, pause threads, reorder merges, and crash between state and provenance commits. A selection that wins only on clean inputs transfers hidden risk into production.

flowchart TD
    A[Define scale dimensions and boundaries] --> B[Run exact and candidate sweeps]
    B --> C[Locate accuracy resource crossovers]
    C --> D[Repeat across seeds machines and merge trees]
    D --> E[Check confidence calibration]
    E --> F[Inject replay loss corruption saturation]
    F --> G[Slice failures by workload regime]
    G --> H{All hard SLOs pass}
    H -->|No| X[Reject or retune]
    H -->|Yes| I[Build Pareto frontier]
    I --> J[Select with cost and risk priorities]
    F --> Y[Repair harness if oracle or injection is invalid]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    class A,B,C,D navy;
    class E,F,G,H purple;
    class I,J teal;
    class X,Y crimson;

Selecting Under SLO, Cost and Risk

An approachable selection might compare exact counts with approximate distinct counting on a school dataset. Exact storage may be cheaper and simpler at hundreds of IDs; approximation becomes attractive only when scale, privacy, or aggregation changes.

At production scale, candidate selection includes network and operations. A sketch with smaller state but expensive merges may miss freshness SLOs. A faster design that lacks version compatibility, privacy support, or replay safety creates migration and incident risk.

Adversarial evaluation matters when keys or queries respond to outputs. A fixed-input accuracy claim does not cover adaptive chosen-key attacks. Similarly, averaging error across tenants can hide catastrophic errors for low-volume or high-value populations.

Selection should use hard feasibility gates first. Among survivors, examine the Pareto frontier. Apply monetary or weighted scoring only after metrics are normalized, uncertainty shown, and stakeholders agree on weights; document sensitivity to plausible weight changes.

Produce an Evidence-Backed Selection

A selection report should be reproducible by someone who disagrees with the conclusion. Include workload provenance and exclusions, oracle semantics, candidate versions and parameters, seed plan, environment, raw metrics, uncertainty, failure cases, feasibility gates, Pareto analysis, cost model, sensitivity analysis, canary plan, and decision owner.