Struct quantiles::CKMS
[−]
[src]
pub struct CKMS<T: Copy> { /* fields omitted */ }
This is an implementation of the algorithm presented in Cormode, Korn, Muthukrishnan, Srivastava's paper "Effective Computation of Biased Quantiles over Data Streams". The ambition here is to approximate quantiles on a stream of data without having a boatload of information kept in memory.
As of this writing you must use the presentation in the IEEE version of the paper. The authors' self-published copy of the paper is incorrect and this implementation will not make sense if you follow along using that version. Only the 'full biased' invariant is used. The 'targeted quantiles' variant of this algorithm is fundamentally flawed, an issue which the authors correct in their "Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams"
Methods
impl<T: Copy + PartialOrd + Debug + Add<Output=T>> CKMS<T>
[src]
fn new(error: f64) -> CKMS<T>
Create a new CKMS
A CKMS is meant to answer quantile queries with a known error bound. If
the error passed here is ε and there have been n
items inserted into
CKMS then for any quantile query Φ the deviance from the true quantile
will be +/- εΦn.
For an error ε this structure will require T*(floor(1/(2*ε)) + O(1/ε log εn)) + f64 + usize + usize words of storage.
Examples
use quantiles::CKMS; let mut ckms = CKMS::<u64>::new(0.001); for i in 1..1001 { ckms.insert(i as u64); } assert_eq!(ckms.query(0.0), Some((1, 1))); assert_eq!(ckms.query(0.998), Some((998, 998))); assert_eq!(ckms.query(0.999), Some((999, 999))); assert_eq!(ckms.query(1.0), Some((1000, 1000)));Run
fn last(&self) -> Option<T>
Return the last element added to the CKMS
Example
use quantiles::CKMS; let mut ckms = CKMS::new(0.1); ckms.insert(1.0); ckms.insert(2.0); ckms.insert(3.0); assert_eq!(Some(3.0), ckms.last());Run
fn sum(&self) -> Option<T>
Return the sum of the elements added to the CKMS
Example
use quantiles::CKMS; let mut ckms = CKMS::new(0.1); ckms.insert(1.0); ckms.insert(2.0); ckms.insert(3.0); assert_eq!(Some(6.0), ckms.sum());Run
fn insert(&mut self, v: T)
Insert a T into the CKMS
Insertion will gradulally shift the approximate quantiles. This implementation is biased toward fast writes and slower queries. Storage may grow gradually, as defined in the module-level documentation, but will remain bounded.
fn query(&self, q: f64) -> Option<(usize, T)>
Query CKMS for a ε-approximate quantile
This function returns an approximation to the true quantile-- +/- εΦn --for the points inserted. Argument q is valid 0. <= q <= 1.0. The minimum and maximum quantile, corresponding to 0.0 and 1.0 respectively, are always known precisely.
Return
Examples
use quantiles::CKMS; let mut ckms = CKMS::<u32>::new(0.001); for i in 0..1000 { ckms.insert(i as u32); } assert_eq!(ckms.query(0.0), Some((1, 0))); assert_eq!(ckms.query(0.998), Some((998, 997))); assert_eq!(ckms.query(1.0), Some((1000, 999)));Run
fn count(&self) -> usize
Query CKMS for the count of its points
This function returns the total number of points seen over the lifetime of the datastructure, not the number of points currently stored in the structure.
Examples
use quantiles::CKMS; let mut ckms = CKMS::<u32>::new(0.001); for i in 0..1000 { ckms.insert(i as u32); } assert_eq!(ckms.count(), 1000);Run
Trait Implementations
impl<T: Debug + Copy> Debug for CKMS<T>
[src]
impl<T: PartialEq + Copy> PartialEq for CKMS<T>
[src]
fn eq(&self, __arg_0: &CKMS<T>) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, __arg_0: &CKMS<T>) -> bool
This method tests for !=
.
impl<T: Clone + Copy> Clone for CKMS<T>
[src]
fn clone(&self) -> CKMS<T>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0
Performs copy-assignment from source
. Read more
impl<T> AddAssign for CKMS<T> where T: Copy + Add<Output=T> + PartialOrd + Debug
[src]
fn add_assign(&mut self, rhs: CKMS<T>)
The method for the +=
operator