jaideeppyne opened a new pull request, #250: URL: https://github.com/apache/datasketches-rust/pull/250
`TDigestView::quantile` passes its two interpolation weights to `weighted_average` in the wrong order. `w1` is the distance from the left edge of the bracket and `w2` the distance to the right edge, but `w1` is paired with `centroids[i]`, so as the requested rank rises inside a bracket the estimate slides toward the *lower* centroid. The reference MergingDigest pairs `mean[i]` with the right-edge distance. This is reachable from plain `update()`. I sampled 1001 evenly spaced ranks on each of 2000 digests of 1000 uniform values at k=100: all 2000 produced at least one rank where `quantile(r)` came out below `quantile` of a smaller rank, worst drop 56.99 on a 0..1000 range. Mean absolute rank error over 200 digests of 10000 values, measured against the true empirical rank of the returned value, goes from 0.011874 to 0.000552 after the fix. Two more, both in the mirrored tail branches: - `quantile` adds where its left-tail mirror subtracts, so the right tail walks *past* `max`. On a digest with centroids `(10,w=10) (50,w=10) (90,w=10)`, min 0, max 100, `quantile(0.9)` returns 105. - `rank` omits the `/ total_weight` normaliser that its right-tail mirror has. The same digest returns `rank(5.0) = 3.0` and `pmf([5.0]) = [3.0, -2.0]`. Both tail branches need a first or last centroid heavier than one. Compression never merges the extreme centroids, so digests built through `update` or `merge` always keep unit-weight tails and never select them. I checked that empirically rather than assuming it: 200 C++ digests of 20000 values each serialized with unit-weight tails every time, and no `update`- or `merge`-built digest in my sweep hit either branch. They are reachable through `deserialize`, including the reference implementation format that `deserialize_compat` accepts, where heavier tails are normal. How I found them: I was diffing quantile family behaviour against the C++ core from the `datasketches` Python package. That does not work here because the C++ core has all three defects too, byte for byte. `tdigest_double.deserialize` of the image above gives rank 3.0, quantile 105.0 and pmf `[3.0, -2.0]`, identical to Rust. So I used invariants instead as the oracle: quantiles non-decreasing in rank and inside `[min, max]`, ranks inside `[0, 1]` and non-decreasing in value, PMF masses non-negative and summing to 1. Sweep was 3000 digests, a third from `update`, a third from twenty merges, a third deserialized with random centroid weights, 501 ranks and 501 values each. Zero violations after the fix, and I confirmed the pre-fix code violates every one of those except the left-tail rank normaliser, which only the deserialized third can reach. The same three are open against Java as apache/datasketches-java#755. Please note this makes Rust disagree with the current C++, Java and Go ports on `quantile` for any digest with more than one centroid. I think correctness wins here since the current output is not even monotonic, but it is a real cross-language divergence until the other ports land the same change, so tell me if you would rather hold this. Tests: three exact-value cases pinning each branch, plus `property.rs` with quickcheck properties for quantile monotonicity from `update` and from `merge`, and for the CDF/PMF invariants. Five of the six fail on the current source with the tests kept in place. `prop_cdf_is_a_distribution` passes before and after because the left-tail rank branch is not reachable from `update`; the exact-value test covers that one. Full `cargo test --workspace` is green, including the cpp/java/go serde snapshots, and `cargo x lint` passes except `hawkeye`, which will not install on the pinned 1.86 toolchain. Not covered: the dead interpolation block after the loop in `quantile`. I instrumented it with a panic and it was never reached across the 3000-digest sweep, since the guarded tail branch and the `weight > total - 1` early return between them cover the whole range. I left it alone rather than change unreachable code. I used Claude Code to help investigate and write this. -- 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]
