Repository navigation
T-Digest: merge() silently corrupts min/max #277
Description
I asked Claude to look for bugs and it reported this against the T-digest merge operation
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?
Activity
fix(tdigest): preserve min/max when merging digests
jaideeppyne commentedon Sep 16, 2026
Yes — it's a real bug, but it only shows up when the extreme centroids have weight > 1.
Compression never merges the extreme centroids for digests built through
update, so min/max stay equal to those centroid means and a merge looks fine. Deserialized images (including the reference-format ones) can store min/max strictly outside the extreme centroid means.mergethen re-derives extrema from those means and the tails drift.Fix is to copy the stored min/max from the other digest before compressing. PR: #280