[PR] Fix swapped interpolation weights and right tail sign in tdigest Quantile [datasketches-go]

["jaideeppyne (via GitHub)" <gi...@apache.org>]

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: dev-unsubscribe@datasketches.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org

Re: [PR] Fix swapped interpolation weights and right tail sign in tdigest Quantile [datasketches-go]

["proost (via GitHub)" <gi...@apache.org>]

proost merged PR #171:
URL: https://github.com/apache/datasketches-go/pull/171


-- 
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: dev-unsubscribe@datasketches.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@datasketches.apache.org
For additional commands, e-mail: dev-help@datasketches.apache.org