jaideeppyne opened a new pull request, #171: URL: https://github.com/apache/datasketches-go/pull/171
Two spots in `tdigest.Double.Quantile` differ from the reference implementation ([MergingDigest](https://github.com/tdunning/t-digest/blob/main/core/src/main/java/com/tdunning/math/stats/MergingDigest.java)). The first affects ordinary use, the second needs a decoded sketch. ### The interpolation weights are passed in the wrong order Reference: ```java double z1 = index - weightSoFar - leftUnit; double z2 = weightSoFar + dw - index - rightUnit; return weightedAverage(mean[i], z2, mean[i + 1], z1); ``` We compute the same two quantities as `w1`/`w2` and then call `weightedAverage(d.centroids[i].mean, w1, d.centroids[i+1].mean, w2)`. The weight on `mean[i]` should be the distance to the far end of the bracket, not the near one. As the rank rises inside a bracket the estimate moves toward the lower centroid instead of the upper one. That makes `Quantile` non-monotonic from a plain `Update` sequence. 2000 of 2000 random digests return some `Quantile(r2) < Quantile(r1)` with `r2 > r1`, k in {10, 20, 50, 100, 200}, n in [100, 50000], gaussian / uniform / lognormal. It also shows on the checked-in fixtures: `tdigest_ref_k100_n10000_double.sk` and every `serialization_test_data/cpp_generated_files/tdigest_double_*` file give thousands of descents over 5000 evenly spaced ranks, and 0 after. It costs accuracy too. Rank error against the exact quantiles of the input, 29970 queries at k=100, n=20000 gaussian: ``` mean max before 0.011803 0.042200 after 0.000385 0.002100 ``` ### The right tail branch adds where the reference subtracts Reference is `max - (...)`, we have `d.max + (...)`, so the branch returns quantiles above `MaxValue()`. On min 0, centroids (10,100), (20,100), (30,100), max 40, rank 0.90 returns 45.92 where the reference gives 34.08. This one is not reachable from `Update` or `Merge`. `merge` never lets the first or last centroid absorb a neighbour, so both tails stay singletons and `lastWeight > 1` is false. I looked for a counterexample over 3000 digests built from random updates, merges and encode/decode round trips and never saw a first or last centroid of weight above 1. It is reachable from `DecodeDouble`, which accepts one, so the test builds it that way. `Rank`'s left tail already has the `/ centroidsWeight` normalizer, so there is nothing to change there. That is the one difference from apache/datasketches-java#755, which fixes the same two plus a missing normalizer in `getRank`. Two new tests, each verified failing before its own fix with the tests kept in place. `go test ./...` and `go test -race ./tdigest/` are green before and after, so nothing existing covered this. I used Claude Code on this. The oracles were tdunning's `MergingDigest` and monotonicity, which needs no second implementation. Differential testing against the C++ core would not have found it, since C++ has the same two. -- 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]
