README.md

zw-fast-quantile

A Rust implementation of the Zhang-Wang fast approximate quantile algorithm, as described in An Efficient Quantile Computation Technique for Approximate Query Processing (SSDBM 2007). This is the original algorithm that inspired the quantile techniques used in TensorFlow Boosted Trees. For more context, see this blog post.

Features

• Approximate quantile computation with tunable error bound (epsilon)
• Two variants: fixed-size (known stream length) and unbounded (unknown stream length)
• Generic over any Clone + Ord element type
• Sub-linear memory usage — space grows logarithmically with stream size
• Optional serde support for serialization/deserialization
• Query caching for efficient repeated lookups

Installation

Add this to your Cargo.toml:

[dependencies]
zw-fast-quantile = "1.0"

Usage

FixedSizeEpsilonSummary

Use when the total number of elements is known ahead of time. This allows tighter memory allocation. Inserting more than the declared stream size n panics.

use zw_fast_quantile::FixedSizeEpsilonSummary;

let epsilon = 0.01;  // 1% error tolerance
let n = 10000;       // expected stream size
let mut summary = FixedSizeEpsilonSummary::new(n, epsilon).unwrap();

for value in 1..=n {
    summary.update(value);
}

// Query the median (rank 0.5)
let median = summary.query(0.5).unwrap();

// Query any quantile from 0.0 (min) to 1.0 (max)
let p99 = summary.query(0.99).unwrap();

UnboundEpsilonSummary

Use when the stream size is not known in advance. It splits the stream into sub-streams of geometrically growing length, freezes a compressed summary for each completed sub-stream, and merges them at query time. There is no fixed limit on the number of elements.

use zw_fast_quantile::UnboundEpsilonSummary;

let epsilon = 0.01;
let mut summary = UnboundEpsilonSummary::new(epsilon).unwrap();

// Feed values from any iterator or stream
for value in 1..=10000 {
    summary.update(value);
}

let median = summary.query(0.5).unwrap();
let count = summary.size();  // number of elements inserted

Error Handling

Both constructors and query() return Result<_, QuantileError>:

use zw_fast_quantile::{FixedSizeEpsilonSummary, QuantileError};

// Invalid parameters
assert!(FixedSizeEpsilonSummary::<usize>::new(0, 0.1).is_err());       // n must be > 0
assert!(FixedSizeEpsilonSummary::<usize>::new(10, -0.1).is_err());     // epsilon must be in (0, 1]
assert!(FixedSizeEpsilonSummary::<usize>::new(10, 1.5).is_err());      // epsilon must be in (0, 1]
assert!(FixedSizeEpsilonSummary::<usize>::new(10, f64::NAN).is_err()); // NaN and infinity are rejected

// Query errors
let s = FixedSizeEpsilonSummary::<usize>::new(10, 0.1).unwrap();
assert!(s.query(0.5).is_err());  // EmptySummary — no values inserted

Choosing Epsilon

The epsilon parameter must be in (0, 1] and controls the trade-off between accuracy and memory:

Epsilon	Max Error	Relative Memory
0.1	10%	Lowest
0.01	1%	Moderate
0.001	0.1%	Higher

A query for rank r on a stream of n elements will return an element whose true rank is within r ± epsilon (i.e., the result is within epsilon * n positions of the exact answer).

Very short streams are a special case: when epsilon * n is at most 8, the summary simply keeps every element and answers queries exactly, because the Zhang-Wang block size is not meaningful for such small epsilon * n.

Benchmarks

Benchmarked against GK01 from the quantiles crate with 5,000 values and epsilon = 0.01. Representative Criterion medians from September 2026 (version 1.0.1) are:

Operation	ZW fixed	ZW unbounded	GK01
Insert 5,000 values	21.05 µs	31.32 µs	104.48 µs
Query 10 quantiles, warm cache	96.7 ns	135.3 ns	130.4 ns
Query 10 quantiles, cold cache	1.39 µs	15.16 µs	—

ZW caches its merged query summary after the first query. The warm-cache rows measure repeated lookups; the cold-cache rows clone an uncached, prebuilt summary and include rebuilding that merged summary. Results vary by hardware and toolchain.

Run benchmarks yourself with:

cargo bench

Optional Features

• serde — Enable serialization/deserialization support via serde. Cache fields are skipped during serialization and lazily rebuilt on the next query. The serialized layout is an implementation detail and may change between releases; do not rely on it for long-term storage without pinning the crate version.

  [dependencies]
  zw-fast-quantile = { version = "1.0", features = ["serde"] }

Minimum Supported Rust Version

The MSRV is 1.65.

Documentation

• API docs on docs.rs
• Algorithm internals — how the data structures and operations work
• Architecture overview — code organization and design decisions

Related Projects

• zw-fast-quantile-py — Python bindings for this library

License

Licensed under Apache-2.0.