Crate zw_fast_quantile 

Zhang-Wang fast approximate quantiles algorithm in Rust.

This crate implements the multi-level summary described by Zhang and Wang in An Efficient Quantile Computation Technique for Approximate Query Processing (SSDBM 2007). A summary built with error bound epsilon over n elements answers a rank query r with an inserted element whose position in the sorted stream is within epsilon * n of floor(r * n), while storing far fewer than n elements.

Installation

Add this to your Cargo.toml:

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

Example

use zw_fast_quantile::FixedSizeEpsilonSummary;

let epsilon = 0.1;
let n = 10;
let mut s = FixedSizeEpsilonSummary::new(n, epsilon).unwrap();
for i in 1..=n {
    s.update(i);
}

let ans = s.query(0.0).unwrap();
let expected = 1;
assert!(expected == ans);

use zw_fast_quantile::UnboundEpsilonSummary;

let epsilon = 0.1;
let n = 10;
let mut s = UnboundEpsilonSummary::new(epsilon).unwrap();
for i in 1..=n {
    s.update(i);
}

let ans = s.query(0.0).unwrap();
let expected = 1;
assert!(expected == ans);

Choosing a summary

• FixedSizeEpsilonSummary needs the stream length up front and uses the least memory. Inserting more than the declared number of elements panics.
• UnboundEpsilonSummary accepts any number of elements and grows its summaries as the stream continues.

epsilon must be in (0.0, 1.0]. Very short streams, where epsilon * n is at most 8.0, are stored exactly rather than summarized.

Serialization

With the serde feature both summaries implement Serialize and Deserialize. Query caches are skipped and rebuilt on the next query. The serialized layout is an implementation detail: it can change between releases, and a summary written by one crate version is not guaranteed to load in another.

Structs

FixedSizeEpsilonSummary

An epsilon-approximate quantile summary for a stream with a known size.

UnboundEpsilonSummary

An epsilon-approximate quantile summary for a stream of unknown size.

Enums

QuantileError

Errors that can occur when constructing or querying a quantile summary.