Module quantiles::greenwald_khanna [−] [src]

Greenwald Khanna calculates epsilon-approximate quantiles. If the desired quantile is phi, the epsilon-approximate quantile is any element in the range of elements that rank between lbound((phi-epsilon) x N) and lbound((phi+epsilon) x N)

terminology from the paper:

  • S: set of observations
  • n: number of observations in S
  • v[i]: observation i in S
  • r: rank of observation in S from 1 to n.
  • r_min(v[i]): lower bound on rank r of v[i]
  • r_max(v[i]): upper bound on rank r of v[i]
  • g[i] = r_min(v[i]) - r_min(v[i - 1])
  • delta[i] = r_max(v[i]) - r_min(v[i])
  • t[i] = tuple(v[i], g[i], delta[i])
  • phi: quantile as a real number in the range [0,1]
  • r: ubound(phi * n)

identities:

  • r_min(v[i]) = forall j<=i sum of g[j]
  • r_max(v[i]) = ( forall j<=i sum of g[j] ) + delta[i]
  • g[i] + delta[i] - 1 is an upper bound on the total number of observations
  • between v[i] and v[i-1]
  • sum of g[i] = n

results:

  • max_i(g[i] + delta[i]) <= 2 * epsilon * n
  • a tuple is full if g[i] + delta[i] = floor(2 * epsilon * n)

@inproceedings{Greenwald:2001:SOC:375663.375670, author = {Greenwald, Michael and Khanna, Sanjeev}, title = {Space-efficient Online Computation of Quantile Summaries}, booktitle = {Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data}, series = {SIGMOD '01}, year = {2001}, isbn = {1-58113-332-4}, location = {Santa Barbara, California, USA}, pages = {58--66}, numpages = {9}, url = {http://doi.acm.org/10.1145/375663.375670}, doi = {10.1145/375663.375670}, acmid = {375670}, publisher = {ACM}, address = {New York, NY, USA}, }

Examples

use quantiles::greenwald_khanna::*;

let epsilon = 0.01;

let mut stream = Stream::new(epsilon);

let n = 1001;
for i in 1..n {
    stream.insert(i);
}
let in_range = |phi: f64, value: u32| {
  let lower = ((phi - epsilon) * (n as f64)) as u32;
  let upper = ((phi + epsilon) * (n as f64)) as u32;
  (epsilon > phi || lower <= value) && value <= upper
};
assert!(in_range(0f64, *stream.quantile(0f64)));
assert!(in_range(0.1f64, *stream.quantile(0.1f64)));
assert!(in_range(0.2f64, *stream.quantile(0.2f64)));
assert!(in_range(0.3f64, *stream.quantile(0.3f64)));
assert!(in_range(0.4f64, *stream.quantile(0.4f64)));
assert!(in_range(1f64, *stream.quantile(1f64)));

Structs

Stream

The summary S of the observations seen so far.
Tuple

3-tuple of a value v[i], g[i] and delta[i].

Functions

find_insert_pos

Locates the proper position of v in a vector vs such that when v is inserted at position i, it is less then the element at i+1 if any, and greater than or equal to the element at i-1 if any.
find_insert_pos_linear

Locates the proper position of v in a vector vs such that when v is inserted at position i, it is less then the element at i+1 if any, and greater than or equal to the element at i-1 if any. Works by scanning the slice from start to end.