apache / apache/datasketches-java

can we use stable sort for tdigest

未关闭
#739 1 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
主要语言
Java
星标
958
派生
226
平均合并
3 天 15 小时
30 天内合并 PR
10

描述

the sort on centroids (v,w) -> (value, weight) in tdigest merge uses the sort based on value (v) and index -> therefore if we have centroids like (200,1)(100,3)(300,2)(100,1) then at merge it can be sorted to 2 states :

1. (100,1)(100,3)(200,1)(300,2)
2. (100,3)(100,1)(200,1)(300,2)

due to which the merging result can differ

other than that we can use sorting based on value (v) and weight (w) as in
https://github.com/tdunning/t-digest/blob/main/core/src/main/java/com/tdunning/math/stats/Sort.java

and this will make the sort stable and remove variance in result

贡献指南

这个仓库没有索引到贡献指南

调研方向

Start in the t-digest merge logic where centroids are sorted by value and index. Compare that ordering with core/src/main/java/com/tdunning/math/stats/Sort.java referenced in the issue, then verify that equal-value centroids are ordered deterministically and produce consistent merge results.

由索引模型根据 Issue 内容生成。

评估

技术栈
java
领域
data
Issue 类型
缺陷
难度
3/5
预计耗时
1-2 天
活跃度
活跃
描述清晰度
基本清楚
新手友好度
58/100

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。