Package org.terracotta.statistics.derived.histogram

Class BarSplittingBiasedHistogram

java.lang.Object
org.terracotta.statistics.derived.histogram.BarSplittingBiasedHistogram
All Implemented Interfaces:
Histogram
public class BarSplittingBiasedHistogram extends Object implements Histogram
An implementation of the histogram algorithm described in: 'Fast Computation of Approximate Biased Histograms on Sliding Windows over Data Streams' [H. Mousavi & C. Zaniolo]

This class is *not thread-safe*, safe consumption in a multi-threaded environment will require some form of external locking.

See Also:

  • Field Details

    • DEFAULT_MAX_COEFFICIENT

      private static final double DEFAULT_MAX_COEFFICIENT
      See Also:

    • DEFAULT_PHI

      private static final double DEFAULT_PHI
      See Also:

    • DEFAULT_EXPANSION_FACTOR

      private static final int DEFAULT_EXPANSION_FACTOR
      See Also:

    • DEFAULT_EXP_HISTOGRAM_EPSILON

      private static final double DEFAULT_EXP_HISTOGRAM_EPSILON
      See Also:

    • barCount

      private final int barCount

    • bucketCount

      private final int bucketCount

    • barEpsilon

      private final double barEpsilon

    • window

      private final long window

    • phi

      private final double phi

    • alphaPhi

      private final double alphaPhi

    • ratio

      private final double ratio

    • bars

      private final List<BarSplittingBiasedHistogram.Bar> bars

    • maxSizeTable

      private final double[] maxSizeTable

    • size

      private long size

  • Constructor Details

    • BarSplittingBiasedHistogram

      public BarSplittingBiasedHistogram(double maxCoefficient, double phi, int expansionFactor, int bucketCount, double barEpsilon, long window)
      Create a histogram maintained over a sliding time window.

      The constructed histogram is:

      • maintained over window sliding window
      • consists of bucketCount buckets
      • where b1.size() ~= b0.size * phi
      • with each bucket internally composed of expansionFactor bars
      • with each bar maintaining a count accurate with a fractional error of barEpsilon
      • where bars are split when there size exceeds maxCoefficient of their target size
      Parameters:
      maxCoefficient - relative split threshold
      phi - histogram bucket bias factor
      expansionFactor - number of bars per bucket
      bucketCount - number of buckets
      barEpsilon - bar count relative error
      window - sliding window size

    • BarSplittingBiasedHistogram

      public BarSplittingBiasedHistogram(int bucketCount, long window)
      Create a histogram maintained over a sliding time window.

      The constructed histogram is:

      • maintained over window sliding window
      • consists of bucketCount buckets
      • where b1.size() ~= b0.size * 0.7
      Parameters:
      bucketCount - number of buckets
      window - sliding window size

    • BarSplittingBiasedHistogram

      public BarSplittingBiasedHistogram(double phi, int bucketCount, long window)
      Create a histogram maintained over a sliding time window.

      The constructed histogram is:

      • maintained over window sliding window
      • consists of bucketCount buckets
      • where b1.size() ~= b0.size * phi
      Parameters:
      phi - histogram bucket bias factor
      bucketCount - number of buckets
      window - sliding window size

  • Method Details

    • event

      public void event(double value, long time)
      Record an event of the given value occuring at he given time
      Specified by:
      event in interface Histogram
      Parameters:
      value - event value
      time - event time

    • expire

      public void expire(long time)
      Expire old events from all buckets.
      Specified by:
      expire in interface Histogram
      Parameters:
      time - current timestamp

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • getBuckets

      public List<Histogram.Bucket> getBuckets()
      Description copied from interface: Histogram
      Returns the histograms buckets
      Specified by:
      getBuckets in interface Histogram
      Returns:
      the histogram buckets

    • nextUpIfEqual

      protected static double nextUpIfEqual(double test, double value)

    • getMinimum

      public double getMinimum()
      Description copied from interface: Histogram
      The minimum value.

      This is equal to the inclusive lower bound of the zeroth (0.0) quantile.

      Specified by:
      getMinimum in interface Histogram
      Returns:
      the minimum value

    • getMaximum

      public double getMaximum()
      Description copied from interface: Histogram
      The maximum value.

      This is equal to highest double value strictly less than the exclusive upper bound of the last (1.0) quantile.

      Specified by:
      getMaximum in interface Histogram
      Returns:
      the maximum value

    • getQuantileBounds

      public double[] getQuantileBounds(double quantile)
      Description copied from interface: Histogram
      Returns the bounds [minimum, maximum) on the given quantile.
      Specified by:
      getQuantileBounds in interface Histogram
      Parameters:
      quantile - desired quantile
      Returns:
      the quantile bounds

    • evaluateQuantileFromMax

      private double[] evaluateQuantileFromMax(double quantile)

    • evaluateQuantileFromMin

      private double[] evaluateQuantileFromMin(double quantile)

    • maxBarSize

      private double maxBarSize(int barIndex)

    • split

      private void split(BarSplittingBiasedHistogram.Bar x, int xIndex)

    • mergeBars

      private int mergeBars()

    • getBarIndex

      private int getBarIndex(double value)

    • size

      public long size()
      Specified by:
      size in interface Histogram
      Returns:
      the number of elements in the histogram

    • bars

      List<BarSplittingBiasedHistogram.Bar> bars()

    • alphaPhi

      double alphaPhi()

    • phi

      double phi()

    • bucketCount

      int bucketCount()