apache / apache/datasketches-rust

Add owned batch merging to T-Digest

Open
#269 1 comment 0 reactions 0 assignees View on GitHub
good first issue help wanted
Dominant language
Rust
Stars
123
Forks
45
Avg merge
9h 3m
Merged PRs (30d)
52

Description

Aggregation pipelines often own multiple partial `TDigestMut` states. Repeated borrowed `merge` calls recompress intermediate results, so consuming an iterator of digests should combine them with one compression pass while retaining the existing borrowed API.

PR #261 explored `FromIterator`. A first implementation collected sorted slices into a `BinaryHeap` and then collected all centroids again, which added allocations and obscured the data flow. The revised approach lazily k-way merges fully compressed sorted buffers directly into compression; inputs with unsorted update tails are materialized and stably sorted once because sorting every tail separately was slower.

A focused PR should cover empty and single inputs, mixed `k` values, stable tie ordering, compressed and uncompressed inputs, allocation-aware benchmarks, and the clone tradeoff between borrowed `merge` and consuming collection.

Contributor guide

Open the contributing guide

Research direction

Start by tracing the existing borrowed merge API and the TDigestMut compression path, then read PR #261 for the prior FromIterator approach and its allocation tradeoffs. Validate empty and single inputs, mixed k values, stable ties, and compressed or uncompressed inputs; add allocation-aware benchmarks and compare consuming collection with borrowed merge and cloning.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
data
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.