apache / apache/datasketches-java

can we use stable sort for tdigest

Offen
#739 1 Kommentar 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen
Vorherrschende Sprache
Java
Sterne
958
Forks
226
Ø Merge
3 T. 9 Std.
Gemergte PRs (30 T.)
8

Beschreibung

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

Beitragsleitfaden

Für dieses Repository ist kein Beitragsleitfaden indexiert

Rechercherichtung

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.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Bewertung

Tech-Stack
java
Bereich
data
Issue-Typ
Bug
Schwierigkeit
3/5
Geschätzter Aufwand
1-2 Tage
Aktivitätsstatus
Aktiv
Klarheit
Größtenteils klar
Anfängerfreundlichkeit
58/100

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.