📖 Docs

An implementation of the Relative Error Quantiles (REQ) sketch algorithm in Rust.

REQ sketch is a probabilistic data structure for approximate quantile estimation with relative error guarantees, particularly useful for streaming scenarios where you need to estimate quantiles over large data streams with bounded memory usage.

This implementation is based on the paper "Relative Error Streaming Quantiles" by Graham Cormode, Zohar Karnin, Edo Liberty, Justin Thaler, and Pavel Veselý. A lot of inspiration was taken from the C++ implementation in Apache DataSketches https://datasketches.apache.org/docs/REQ/ReqSketch.html

use reqsketch::{ReqSketch, SearchCriteria};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Create a new sketch
    let mut sketch = ReqSketch::new();

    // Add values to the sketch
    for i in 0..10000 {
        sketch.update(i as f64);
    }

    // Query quantiles
    let median = sketch.quantile(0.5, SearchCriteria::Inclusive)?;
    let p99 = sketch.quantile(0.99, SearchCriteria::Inclusive)?;

    println!("Median: {:.2}", median);
    println!("99th percentile: {:.2}", p99);

    // Query ranks
    let rank = sketch.rank(&5000.0, SearchCriteria::Inclusive)?;
    println!("Rank of 5000: {:.4}", rank);

    Ok(())
}

let mut sketch1 = ReqSketch::new();
let mut sketch2 = ReqSketch::new();

// Add data to both sketches
for i in 0..1000 {
    sketch1.update(i as f64);
    sketch2.update((i + 1000) as f64);
}

// Merge sketch2 into sketch1
sketch1.merge(&sketch2)?;

Generate DataSketches-style rank error plots:

# Generate HRA and LRA rank error plots:
cargo run --example req_rank_error --release

# Creates: assets/req_rank_error_hra.png, assets/req_rank_error_lra.png

These plots demonstrate the key REQ characteristic: error tapering toward the optimized tail (rank 1.0 for HRA, rank 0.0 for LRA)

High Rank Accuracy (HRA) Mode:

Low Rank Accuracy (LRA) Mode:

Run the examples to see the sketch in action:

cargo run --example basic_usage

Run performance benchmarks:

# Run all benchmarks
cargo bench

Contributions are welcome! Please feel free to submit a Pull Request.

Licensed under the MIT or Apache License.

• Relative Error Streaming Quantiles Paper
• Apache DataSketches Project
• DataSketches REQ Sketch Documentation