tisonkun opened a new pull request, #310: URL: https://github.com/apache/datasketches-rust/pull/310
Adds feature-gated `UddSketch` for bounded summaries of finite signed `f64` values, with weighted updates, merging, discrete quantiles, a queryable final relative-value error bound, and versioned serialization. The motivation is reproducible aggregation: compatible insertion-only builds produce identical answers and serialized states across input permutations, partition boundaries, and merge trees. ## Design and differences from the papers The implementation follows uniform collapse from [UDDSketch (2020)](https://arxiv.org/abs/2004.08604) and the mergeability argument in [Data stream fusion for accurate quantile tracking and analysis (2021)](https://arxiv.org/abs/2101.06758), with explicit adaptations for the full finite `f64` domain: - **Deterministic initial mapping.** A fixed monotone Q52 approximation `L` replaces platform logarithms. Initial indices use `ceil(L(abs(x)) / (L(1 + alpha) - L(1 - alpha)))`, with specified floating-point evaluation and integer division. Constants and rounding rules are part of UDD1 semantics. - **Translated bucket hierarchy.** Indices are shifted so the smallest positive subnormal has index zero, then coarsened by integer right shifts. This changes pairing alignment from the paper's grid at one. Negative values mirror the positive hierarchy, and zero has its own bucket; a shared budget of at least three buckets therefore accommodates every finite input. New values always traverse the original hierarchy. - **Observed extrema as representatives.** Buckets retain count, minimum, and maximum. Queries use a numerically stable, clamped harmonic mean of the observed magnitudes, rather than representatives derived from ideal powers of gamma. This remains finite at domain extremes and supports a data-dependent error certificate. Counts and extrema combine exactly, without order-dependent floating-point sums. - The API accepts integer weights and rejects non-finite values and count overflow without partial mutation. Storage uses sorted buckets; no runtime dependency is added. ## Merge, error, and decoding contracts Merge requires identical bucket budgets and bit-identical initial accuracy parameters. Reproducibility additionally assumes the same mapping version and states produced through updates, merges, and unmodified serialization roundtrips. At any fixed level, occupied bucket count cannot decrease under insertion. A subset cannot require a coarser level than the full multiset, so every such build reaches the same smallest level fitting the budget. Integer parent mappings compose exactly, and count/min/max combination is associative and commutative. These properties preserve merge consistency despite the translated grid and observed representatives. Deletions are outside this contract. Queries approximate the lower discrete quantile, at zero-based index `floor(q * (n - 1))`; endpoints return the exact extrema. For a nonzero true quantile `x` and returned value `y`, `relative_error()` certifies `abs(y - x) / abs(x)`, including rounding and subnormal effects. True zero is returned exactly. This is a **relative value-error** guarantee, not a rank-error or interpolated-percentile guarantee. Initial accuracy is a target, not an unconditional bound: uniform collapse can widen it, and callers should use the reported final bound even before collapse. UDD1 is Rust-specific: a 32-byte header plus 32 bytes per retained bucket. It claims neither TCK nor Timescale wire compatibility. Deserialization validates structure, counts, ordering, extrema, and their mapping, but cannot establish construction history or the minimal compaction level. Structurally valid externally constructed, overcompacted images are accepted and may remain coarser than a direct replay of their original inputs. The optimizations preserve this UDD1 mapping and layout: corrected integer reciprocal division, exactly equivalent power-of-two scaling of polynomial operands, lookup using observed bucket intervals, and decoding with validated preallocation, fixed-size chunks, and one mapping evaluation for equal extrema. No compact replacement format or Timescale code/dependency is included. ## Validation - `cargo x check`, `cargo x test` (800 tests, including doctests), and `cargo x lint` pass on the PR head after rebasing onto current upstream. - Additional pre-rebase validation: MSRV `cargo +1.86.0 check -p datasketches --all-features`; release-mode mapping tests and the UDDSketch/serialization integration targets. - Committed regressions cover reciprocal correction at integer boundaries, equivalence to the unscaled mapping, frozen UDD1 bucket boundaries, exponent/segment/subnormal transitions, observed-interval and gap updates, saturated weights, merge permutations/trees, error bounds, malformed images, and accepted externally coarsened states. - The comparison harness was exercised at 100,001 rows across seven distributions, 128 input/partition/merge layouts, and six query ranks: no UDDSketch answer or serialized-state differences; all 126 reported UDDSketch error measurements stayed within their certificates. Earlier 100,000- and 1,000,000-row runs also passed the UDDSketch stability and error checks. ## Performance evidence Paired local microbenchmarks compare the final implementation against a temporary pre-optimization snapshot of the **same Q52 mapping**, not a released UDDSketch or t-digest baseline. Environment: Apple M4 Max, macOS 26.6.2, aarch64 release builds, rustc 1.101.0-nightly (8006091eb, 2026-10-17). Identical seeded inputs; two warmup pairs followed by 15 measured pairs, alternating execution order; medians below. Build is ns/input, decode is ns/state. | Workload | Build before → after | Decode before → after | Serialized bytes | | --- | ---: | ---: | ---: | | Lognormal, 1M, 512 buckets, alpha 0.01 | 13.593 → 8.066 | 4,369.812 → 3,205.209 | 13,856 | | Lognormal, 1M, 2,048 buckets, alpha 0.001 | 16.052 → 11.286 | 19,570.000 → 14,301.792 | 63,296 | | Uniform, 1M, 512 buckets, alpha 0.01 | 13.890 → 8.012 | 2,763.709 → 1,986.271 | 8,928 | | Ascending, 1M | 13.861 → 7.880 | 2,955.167 → 2,123.396 | 9,344 | | Subnormal, 100K | 14.310 → 9.283 | 4,107.895 → 2,942.312 | 13,248 | | Empty | — | 10.208 → 11.334 | 32 | The default lognormal build improved about 41%, and large-state decoding about 27%. Tradeoffs: the cached reciprocal adds eight inline bytes per sketch, empty decoding was about 1.1 ns slower, and serialized sizes are unchanged. These synthetic in-memory results exclude database scheduling and I/O and do not establish a universal advantage over other sketches. The committed comparison harness separately compares UDDSketch with current t-digest and pinned t-digest 0.5.0, reporting timing, memory estimates, serialized size, value/rank errors, and stability: ```sh cargo run --release -p benchmarks --example quantile_comparison QUANTILE_ROWS=1000000 cargo run --release -p benchmarks --example quantile_comparison cargo bench -p benchmarks --bench benchmarks -- uddsketch ``` This PR is intentionally a draft for review of the mapping, error, and serialization contracts. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
