reqsketch 0.1.1

Relative Error Quantiles sketch
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

# reqsketch-rs 

[![Crates.io][crates-badge]][crates-url]
[![MIT / Apache 2.0 licensed][license-badge]][license-url]
[![Build Status][actions-badge]][actions-url]

[crates-badge]: https://img.shields.io/crates/v/reqsketch.svg
[crates-url]: https://crates.io/crates/reqsketch
[license-badge]: https://img.shields.io/crates/l/reqsketch.svg
[license-url]: https://github.com/pmcgleenon/reqsketch-rs/blob/main/LICENSE
[actions-badge]: https://github.com/pmcgleenon/reqsketch-rs/actions/workflows/rust.yml/badge.svg
[actions-url]: https://github.com/pmcgleenon/reqsketch-rs/actions?query=workflow%3Arust+branch%3Amain

[📖 Docs](https://docs.rs/reqsketch)

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"](https://arxiv.org/abs/2004.01668) 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

### Basic Usage

```rust
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

```rust
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:

```bash
# 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:**
![REQ Rank Error - HighRank](assets/req_rank_error_hra.png)

**Low Rank Accuracy (LRA) Mode:**
![REQ Rank Error - LowRank](assets/req_rank_error_lra.png)

## Examples

Run the examples to see the sketch in action:

```bash
cargo run --example basic_usage
```

## Benchmarks

Run performance benchmarks:

```bash
# 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](https://arxiv.org/abs/2004.01668)
- [Apache DataSketches Project](https://datasketches.apache.org/)
- [DataSketches REQ Sketch Documentation](https://datasketches.apache.org/docs/Quantiles/ReqSketch.html)