t-digest

A Rust implementation of the t-digest data structure for accurate online accumulation of rank-based statistics such as quantiles and trimmed means, using a variant of 1-dimensional k-means clustering.

This implementation follows Facebook's folly TDigest.

Features

• Accurate quantile estimation with bounded error, especially at the tails (p99, p999)
• Mergeable -- combine digests computed on different machines or threads
• Compact -- fixed memory footprint regardless of input size
• No dependencies by default (optional serde support behind a feature flag)
• no_std + alloc support, including serde without its std feature

Installation

Add this to your Cargo.toml:

[dependencies]
tdigest = "1.0"

Optional features

[dependencies]
tdigest = { version = "1.0", features = ["serde"] }

Quick start

use tdigest::TDigest;

// Create a digest with a compression factor of 100
let t = TDigest::new_with_size(100);

// Feed it one million values
let values: Vec<f64> = (1..=1_000_000).map(f64::from).collect();
let t = t.merge_sorted(values);

// Estimate quantiles
let p99 = t.estimate_quantile(0.99).unwrap();
let expected = 990_000.0;
assert!((expected - p99).abs() / expected < 0.01);

Usage

Creating a digest

use tdigest::TDigest;

// With explicit compression factor (controls accuracy vs. memory)
let t = TDigest::new_with_size(100);

// With default settings (max_size = 100)
let t = TDigest::default();

Adding data

use tdigest::TDigest;

let t = TDigest::new_with_size(100);

// Pre-sorted data (fastest)
let sorted = vec![1.0, 2.0, 3.0, 4.0, 5.0];
let t = t.merge_sorted(sorted);

// Unsorted data (sorts internally)
let unsorted = vec![5.0, 3.0, 1.0, 4.0, 2.0];
let t = t.merge_unsorted(unsorted);

For streaming ingestion, use the buffered mutable API and flush before a centroid-based query:

use tdigest::TDigest;

let mut t = TDigest::new_with_size(100);
for value in [5.0, 3.0, 1.0, 4.0, 2.0] {
    t.push(value);
}
t.flush();
assert_eq!(t.estimate_quantile(0.5), Some(3.0));

Querying

use tdigest::TDigest;

let t = TDigest::new_with_size(100);
let t = t.merge_sorted(vec![1.0, 2.0, 3.0, 4.0, 5.0]);

// Returns None for empty digests, Some(value) otherwise
let median = t.estimate_quantile(0.5);  // ~3.0
let min    = t.min();                    // Some(1.0)
let max    = t.max();                    // Some(5.0)
let mean   = t.mean();                   // Some(3.0)
let count  = t.count();                  // 5.0
let sum    = t.sum();                    // 15.0

Merging digests (distributed / parallel use)

use tdigest::TDigest;

// Build digests independently (e.g. on different threads)
let mut digests = Vec::new();
for chunk in data.chunks(1000) {
    let t = TDigest::new_with_size(100);
    let t = t.merge_sorted(chunk.to_vec());
    digests.push(t);
}

// Merge into a single digest
let combined = TDigest::merge_digests(digests);
let p99 = combined.estimate_quantile(0.99);

Serialization (serde)

Enable the serde feature, then use any serde-compatible format. The deprecated use_serde alias remains available for existing users.

use tdigest::TDigest;

let t = TDigest::new_with_size(100);
let t = t.merge_sorted(vec![1.0, 2.0, 3.0]);

let json = serde_json::to_string(&t).unwrap();
let restored: TDigest = serde_json::from_str(&json).unwrap();

Compression factor

The max_size parameter controls the trade-off between accuracy and memory:

Larger values produce more centroids, giving better accuracy at the cost of more memory and slightly slower merges. A value of 100 is sufficient for most use cases.

Minimum Supported Rust Version (MSRV)

Rust 1.62 -- verified in CI.

no_std

Disable default features to use the crate with alloc but without std:

[dependencies]
tdigest = { version = "1.0", default-features = false }

Serde also works in this configuration by adding features = ["serde"].

Accuracy

Run cargo run --release --example accuracy to compare estimated and exact quantiles across deterministic uniform, normal, lognormal, exponential, bimodal, and adversarial distributions. See architecture and internals for a summary of the measured error profile.

Benchmarks

Run cargo bench to measure sorted and unsorted batch ingestion, incremental ingestion, digest merging, quantile queries, and compression-size sensitivity. The benchmark inputs use fixed random seeds so results can be compared across changes. Run cargo run --release --example accuracy for the accuracy harness.

Documentation

• API docs on docs.rs
• Architecture and internals

License

Apache-2.0 -- see LICENSE for details.