Struct CompactHistogram

pub struct CompactHistogram { /* private fields */ }

CompactHistogram is a fixed-size representation of a histogram. The set of possible labels are partitioned into logarithmically scaled ranges, then further subdivided into equally sized sub-ranges (equally sized within a given range). A CompactHistogram stores a counter for each of the larger logarithmic ranges and which of the equally sized sub-ranges contains the frequency-weighted average of the labels. It is associated with CompactParams.

There are 3 parameters that govern this process:

• n -> the number of logarithmically sized ranges to represent
• k -> the number of equally sized sub-ranges that each larger range is divided into
• b -> a floating point number that determines the size of each of the logarithmically scaled buckets. The ranges are [1..b], [b+1..b^2], …, [b^(n)+1,b^(n+1)].

Each compact histogram can be stored in n * (c + log_2(k)) + c bits, where c is the number of bits dedicated to a counter. Note that this value is independent of b.

This histogram also keeps track of how many labels “overflow”, i.e. are too large to fit into any of the ranges. The labels themselves are lost, but the frequencies are recorded and included in total.

A CompactHistogram must be derived from a StandardHistogram using the to_compact function.

Trait Implementations

impl Histogram<CompactParams, usize, usize> for CompactHistogram

fn labels( &self, params: &CompactParams, ) -> Option<Box<dyn Iterator<Item = usize>>>

If possible, creates and returns an iterator for the labels for which the histogram has frequencies stored.

fn frequency(&self, label: usize, params: &CompactParams) -> Option<usize>

If possible, returns the frequency of a particular label. The behavior need only be defined if the label is in the set of values returned from labels.

fn total(&self) -> usize

the total number of data-points in the histogram