Add posterior (query-time) error estimation for CMS/CountSketch, per Chen et al. IMC'21

[zzylol]

Summary

"Precise Error Estimation for Sketch-based Flow Measurement" (Chen, Wu, Yang, Jiang, Liu — IMC '21) proposes a posterior (query-time, after-the-fact) error estimator for Count-Min Sketch, Count-Sketch, and CU-Sketch that uses the sketch's actual counter values at query time, instead of the traditional a priori worst-case bound derived before measurement starts, obliviously to the real data distribution.

This maps directly onto two SketchKind variants this codebase already has: SketchKind::Cms ("Count-Min Sketch, (ε,δ)-accurate frequency queries") and SketchKind::CountSketch ("Count-Sketch, balanced/zero-mean-error frequency queries") — crates/types/src/post_asap/sketch.rs. The paper's headline numbers (20-700x tighter than the traditional worst-case bound, 0.8-14% deviation from ground truth vs. 2000-4400% for the original bound, across CAIDA/DC/MACCDC real traces and synthetic Zipf workloads) are specifically about the technique this codebase's own cms_width(eps)/cms_depth(delta) sizing formulas (crates/asap-aware-mapping/src/boundary.rs::default_size_params) currently rely on — the exact traditional a priori bound the paper is critiquing.

The technique (Algorithm 1, §3)

For a Count-Min sketch with r rows and w counters/row, given a target confidence 1-δ: pick one row, sort its w counters in descending order, and use the ⌊δ^(1/r) · w⌋-th largest counter value as the error bound for any flow's estimate, valid with confidence 1-δ. The paper proves (§3.2, Theorems 3.1/3.2/3.4) this bound closely approximates the true ground-truth error bound (bias vanishes as O(1/√w)), and is always at least as tight as the traditional bound (Eq. 6). The same idea generalizes to Count-Sketch and CU-Sketch (paper's Appendix A.1, not reproduced in what I fetched — worth reading directly before implementing).

Two ways this could plug into ASAPPlanner — needs a decision, not obvious which (or both)

1. Runtime/readout-time accuracy reporting. Report a query's actual estimated error (via this posterior estimator, computed from the real counter values at readout) alongside its point estimate, rather than only ever being able to state the AccuracyTarget the sketch was originally planned for. For a skewed workload, this could be a much more honest, much tighter confidence statement than "this sketch was sized for ε=0.01" — directly serving this repo's stated interest in resource/accuracy tradeoffs (cost_model.rs, boundary.rs's whole reason for existing).
2. Tighter sizing at plan time. If a deployment is willing to trade the strict a priori worst-case guarantee for an expected-case one, default_size_params's cms_width/cms_depth could potentially size a smaller CMS/CountSketch upfront for a typical (non-adversarial, e.g. Zipf-skewed) workload while still expecting the posterior-estimated runtime error to land within target most of the time — this is a real cost/correctness tradeoff a maintainer needs to explicitly weigh in on, not something to default into silently.

What this needs before implementation

• Access to a sketch's raw counter array at query time, not just its merged readout value — check whether whatever CMS/CountSketch implementation this repo uses (or plans to use — I haven't checked whether an actual sketch library is vendored yet, vs. SketchKind/SketchParams currently being planning-time-only metadata) exposes that internal state, since the estimator needs to sort and rank real counter values, not just read out an aggregate.
• A decision on which of the two integration points above (or both) is wanted.
• Reading the paper's Appendix A.1 for the Count-Sketch/CU-Sketch variant of the algorithm (only §3's CM-specific version was available in what I fetched here).

Related

• crates/types/src/post_asap/sketch.rs — SketchKind::Cms, SketchKind::CountSketch
• crates/asap-aware-mapping/src/boundary.rs — default_size_params, cms_width, cms_depth
• crates/asap-aware-mapping/src/cost_model.rs — where a sizing-tradeoff decision (integration point 2) would plug in

[zzylol]

#248 closes part of this — a note on why it's only part, not a punt.

This issue scoped out two separate integration points and left picking between them (or both) an explicit open decision, plus flagged as unchecked whether this repo even has a real sketch runtime to attach to vs. SketchKind/SketchParams being planning-time-only metadata.

#248 checked, and that resolved unfavorably for one of the two points: a workspace-wide grep for struct.*Cms, impl.*Cms, or any counter-array type turns up nothing. crates/types/src/post_asap/sketch.rs's SketchKind/SketchParams and boundary.rs's cms_width/cms_depth are purely planning-time sizing numbers — there is no real sketch object anywhere in this codebase with an actual counter array to read at query time. So:

• Runtime/readout-time accuracy reporting (integration point 1) — not attempted. There's nothing to wire it into yet.
• Tighter plan-time sizing (integration point 2) — implemented for real: boundary.rs::posterior_aware_size_params, opt-in and purely additive alongside default_size_params.
• The estimator math itself (Algorithm 1/2/3 for CM-Sketch, CU-Sketch, and Count-Sketch, from §3 and Appendix A.1) is implemented as plain functions over &[u64]/&[i64] counter slices in the new asap_types::post_asap::error_estimation — deliberately sketch-object-agnostic, so whatever eventually provides real counter arrays can call these directly with no changes needed here.

So this issue should stay open, scoped down to just the runtime wiring: land a real CMS/Count-Sketch/CU-Sketch implementation with an inspectable counter array, then call error_estimation's functions from its readout path. The estimator side of that work is already done and waiting.

[zzylol]

Related open work

• Provides runtime error evidence consumed by replanning in Feed observed posterior sketch error back into re-planning (execution-time → planning-time loop) #250.
• May support safe approximate roll-up checks in Support accuracy-aware approximate Count roll-ups #278.
• General nested approximate-error propagation remains tracked by Propagate end-to-end accuracy guarantees for approximate-over-approximate plans #172.