Crate subms_count_min_sketch 

Count-Min Sketch with conservative update and Kirsch-Mitzenmacher hashing.

d rows of w counters; each insert increments only the minimum cell(s) across the d rows. Query returns the minimum cell across the d rows. Width is rounded up to a power of two so indexing is a bitmask, not a %.

Estimates are one-sided: estimate(k) >= true_count(k) always, with the over-count bounded by relative_error() * total() at confidence().

use subms_count_min_sketch::CountMinSketch;

// Size from the error budget rather than guessing (d, w): 0.1% of the
// stream volume, 99.9% of the time.
let mut cms = CountMinSketch::with_error_bounds(0.001, 0.999);
for _ in 0..1000 { cms.add("ESZ5"); }
for i in 0..50_000 { cms.add_u64(i); }

let est = cms.estimate("ESZ5");
assert!(est >= 1000);
assert!(cms.estimate_lower_bound("ESZ5") <= 1000);
assert_eq!(cms.total(), 51_000);

// Checkpoint and restore without a serialization dependency.
let bytes = cms.to_bytes();
let restored = CountMinSketch::from_bytes(&bytes).unwrap();
assert_eq!(restored.estimate("ESZ5"), est);

Not thread-safe. Every mutator takes &mut self, so a shared sketch needs external synchronisation; the intended concurrent shape is one sketch per writer thread folded with the merge feature at the join.

Full writeup, design notes and measured benchmarks: https://www.submillisecond.com/cookbook/recipes/subms-count-min-sketch

Re-exports

pub use features::heavy_hitters::HeavyHitters;

pub use features::merge::MergeError;

pub use features::merge::merge_disjoint_into;

pub use features::merge::merge_into;

pub use features::windowed::WindowedCountMinSketch;

Modules

features

Opt-in feature catalog. Each submodule is gated by its own Cargo feature flag and adds a specific capability to the base sketch without bloating the core build.

recipe

SubMsRecipe impl.

Structs

CountMinSketch

Enums

SnapshotError

Why a byte slice could not be decoded into a sketch.

Constants

MAX_DEPTH

Row cap. The add path keeps its index set in a fixed stack array, and d = 16 already puts the failure probability at e^-16, so a deeper sketch buys nothing a wider one would not buy more cheaply.