apache / apache/datasketches-rust

T-Digest: merge() silently corrupts min/max

Open
#277 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
123
Forks
45
Avg merge
9h 3m
Merged PRs (30d)
52

Description

I asked Claude to look for bugs and it reported this against the [T-digest merge operation](https://github.com/apache/datasketches-rust/blob/main/datasketches/src/tdigest/sketch.rs#L337-L345)

> T-Digest merge() silently corrupts min/max — HIGH
datasketches/src/tdigest/sketch.rs:337-345
// merge() never reads other.min / other.max —
// it infers them from compress_sorted_centroids(), which takes
// the extreme centroids' *means*, not their true min/max
T-Digest already stores explicit min/max fields — a correct merge just needs self.min = self.min.min(other.min). Instead it re-derives them from centroid means, which is only exact when the extreme centroids have unit weight. After ordinary compression this need not hold. Result: min_value()/max_value() drift, and rank()'s tail-interpolation formula silently degrades. This is a pure merge-algorithm defect — the input digest doesn't need to be malformed in any way, just legitimately compressed.

Does this seem like a valid bug?

Contributor guide

Open the contributing guide

Research direction

Start in datasketches/src/tdigest/sketch.rs at the merge operation around lines 337–345, then inspect how the stored min/max values and compressed extreme centroids are used. Reproduce the issue with legitimately compressed digests whose extreme centroids have weight greater than one, and verify that merging preserves min_value(), max_value(), and rank() tail interpolation.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
72/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.