Skip to content

Optimizer: CMS accuracy constraint (ACC) using accuracy_sla #526

Description

@milindsrivastava1997

Part of #523 (Track 3: non-empirical gap 2). Depends on #525's profiling pass for the sample/total-weight query.

  • Implement Error(a,g,θ_a) ≤ ε_a for CMS only (analytic ε-δ guarantee); every other sketch family stays unconstrained for now — same as today, not a regression. Extending sketch-bench's cardinality sweep to unlock empirical Error for other families is separate follow-up work.
  • ε_a = the existing (currently dead) ControllerOptions.accuracy_sla field, threaded through extract_aqes onto AQE/QueryRequirements. 0.0 default (today's serde default, already flagged by warn_default_slas) means "unconfigured" → treat as unconstrained, skip (ACC).
  • Semantics: accuracy_sla is relative-to-true-value percentage error, not CMS's native L1-relative ε. Converting requires ‖f‖₁/true-value — get both from a single live sample of the AQE's own query_strings against Prometheus, in the same profiling pass as Optimizer: real N_g via Prometheus profiling, hints fallback #525's N_g query (also needs the hints-fallback treatment for offline testing).

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions