apache / apache/datasketches-rust
T-Digest: merge() silently corrupts min/max
- 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
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