`std.sketch`

Bounded summaries for streams too large to retain. These pure-Plenty algorithms own their memory and random state. They do not wrap Apache DataSketches or share its serialized formats. Also see xor filters and cuckoo filters.

from std.sketch import SketchError, hyperloglog, hash_u64, quantiles

def main() -> Result[(), SketchError | AllocError | IoError | ZeroDivisionError]:
    mut users = hyperloglog()?
    mut latency = quantiles()?
    for i in range(10000):
        user = u64(i % 2500)
        users.add(hash_u64(user))
        latency.add(f64(i % 100))?
    print(f"about {users.estimate():.0f} distinct users"?)?
    print("median", latency.quantile(0.5)?, "max", latency.quantile(1.0)?)?
    Ok(())

about 2511 distinct users
median 47.0 max 99.0

Distinct identities

hyperloglog(precision=12, seed=0) creates a dense HyperLogLog. Precision is 4–18; storage is exactly 2**precision packed one-byte registers plus Bytes metadata. add(key: u64) and merge(other) allocate nothing. Duplicate keys are harmless. Merge requires equal precision and seed and leaves the receiver unchanged on SketchError.Incompatible. Estimate and merge cost O(registers).

estimate() uses the original HyperLogLog harmonic estimate with linear counting for small cardinalities. relative_standard_error() returns 1.04/sqrt(m): an asymptotic standard error, not a guaranteed error bound. There is no HLL++ bias table or near-64-bit-universe correction. Use this for ordinary cardinality estimation, not exact counts or estimates approaching the hash-space size. See the HyperLogLog paper.

Keys are numeric identities. hash_u64(key, seed=0) is a stable SplitMix64 mixer, not a cryptographic hash. The algorithms are designed for ordinary data, not adversarially chosen keys. Applications mapping text or compound values to u64 must choose and persist their own stable hash convention; collisions in that mapping cannot be undone by a sketch.

Quantiles

quantiles(capacity: Positive[i64] = 1024, seed=0) creates Quantiles, a uniform sample without replacement using reservoir Algorithm R. Capacity is up to 1,048,576 finite f64 values; a larger capacity traps. add(value) rejects NaN/infinities; count() is the number of accepted values and retained() is at most capacity. Construction reserves the sample buffer; updates allocate nothing, maintain it in sorted order, and cost O(capacity) when replacing a sample. Queries cost O(1).

quantile(fraction) accepts a finite number in [0,1]. Empty streams return SketchError.Empty. Endpoints return the exact minimum/maximum. Other fractions use the nearest-rank order statistic of the retained sample (no interpolation). Results are exact before sampling starts. Afterwards they are probabilistic; there is no deterministic rank-error guarantee or tail-relative guarantee. Increase capacity to improve accuracy. This first API has no quantile merge. It is a simple reservoir, not KLL, REQ, or a t-digest.

The sketch owns a std.random.Rng. The seed, accepted input order, and capacity determine its sample. Serializing and restoring preserves continued sampling. The random generator’s existing version-stability contract is unchanged.

Frequent identities

frequent_items(capacity: Positive[i64] = 128) creates a FrequentItems Misra–Gries summary with up to 65,536 counters; a larger capacity traps. It accepts unit-weight u64 identities; there is no weighted update or merge in this API. Construction allocates two fixed arrays. add(key) and frequency(key) allocate nothing and cost O(capacity).

frequency(key) returns Frequency(key, lower, upper) with deterministic bounds on the true count. error_bound() is the number of full counter decrements, at most count() // (capacity + 1). A missing candidate has lower bound zero and upper bound error_bound(). candidates() allocates a list of retained nonzero counters in storage order, not frequency order. Every key whose true frequency exceeds error_bound() appears in that list. A second pass over the original data can compute exact counts for these candidates.

Errors and persistence

InvalidArgument covers invalid configuration or nonfinite input. Count overflow returns Limit without accepting the update: these numerical counters stay exact, never wrap or saturate, and a rejected update leaves samples, extrema, RNG state and frequency bounds unchanged. Nonfinite quantile input is still InvalidArgument, even when the count is exhausted. Constructors, readers and updates that can also fail for another reason report allocation failure as SketchError.Allocation(cause); candidates() and to_bytes() fail only to allocate and return AllocError. All allocation failures remain recoverable.

to_bytes() writes a versioned Plenty format: PSH1, PSQ1, or PSF1. Integers use little-endian u64 words. Quantile values use 32-byte, space-padded, shortest round-trip scientific ASCII slots; this preserves finite f64 values, including signed zero, without host-endian assumptions. These are checkpoint formats, not interchange formats with third-party sketch libraries.

hyperloglog_from_bytes(data, max_precision=18), quantiles_from_bytes(data, max_capacity: Positive[i64] = 1048576), and frequent_items_from_bytes(data, max_capacity: Positive[i64] = 65536) reject unknown versions, bad lengths, invalid state and trailing bytes. Pass a smaller caller limit when reading untrusted checkpoints. All three readers take a &[u8] view. Validated precision/capacity bounds keep checkpoint sizes and offsets representable; frequent-item accounting is validated against the serialized total before adding each counter. Formats are version-tagged: future incompatible formats need a new version and must not silently reinterpret these bytes. They contain no checksum or authentication; structurally valid corruption can change estimates.

The crate audit for issues #496–#498 found infallible allocations in datasketches 0.5.0 (hll/array8.rs, req/compactor.rs), xorf 0.13.0 (prelude/mod.rs), and scalable_cuckoo_filter 0.5.1 (bits.rs). Small direct implementations keep Plenty’s recoverable allocation policy without a native dependency or ABI.

Acknowledgements

Uses the HyperLogLog algorithm by Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier (2007).
Uses reservoir Algorithm R as described by Jeffrey Vitter (1985).