reqsketch-rs

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

Overview

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

Quick Start

Add this to your Cargo.toml:

[dependencies]
reqsketch = "0.1"

Basic Usage

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(())
}

Sketch Merging

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)?;

REQ Rank Error Analysis

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:

Examples

Run the examples to see the sketch in action:

cargo run --example basic_usage

Benchmarks

Run performance benchmarks:

# Run all benchmarks
cargo bench

Contributing

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

License

Licensed under the MIT or Apache License.

References

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