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 java.lang.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:

Fast Computation of Approximate Biased Histograms on Sliding Windows over Data Streams

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) static class	BarSplittingBiasedHistogram.Bar

Nested classes/interfaces inherited from interface org.terracotta.statistics.derived.histogram.Histogram

Histogram.Bucket

Field Summary

Fields

Modifier and Type	Field	Description
private double	alphaPhi
private int	barCount
private double	barEpsilon
private java.util.List<BarSplittingBiasedHistogram.Bar>	bars
private int	bucketCount
private static double	DEFAULT_EXP_HISTOGRAM_EPSILON
private static int	DEFAULT_EXPANSION_FACTOR
private static double	DEFAULT_MAX_COEFFICIENT
private static double	DEFAULT_PHI
private double[]	maxSizeTable
private double	phi
private double	ratio
private long	size
private long	window

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
(package private) double	alphaPhi()
(package private) java.util.List<BarSplittingBiasedHistogram.Bar>	bars()
(package private) int	bucketCount()
private double[]	evaluateQuantileFromMax(double quantile)
private double[]	evaluateQuantileFromMin(double quantile)
void	event(double value, long time)	Record an event of the given value occuring at he given time
void	expire(long time)	Expire old events from all buckets.
private int	getBarIndex(double value)
java.util.List<Histogram.Bucket>	getBuckets()	Returns the histograms buckets
double	getMaximum()	The maximum value.
double	getMinimum()	The minimum value.
double[]	getQuantileBounds(double quantile)	Returns the bounds [minimum, maximum) on the given quantile.
private double	maxBarSize(int barIndex)
private int	mergeBars()
protected static double	nextUpIfEqual(double test, double value)
(package private) double	phi()
long	size()
private void	split(BarSplittingBiasedHistogram.Bar x, int xIndex)
java.lang.String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

DEFAULT_MAX_COEFFICIENT

private static final double DEFAULT_MAX_COEFFICIENT

See Also:

Constant Field Values

DEFAULT_PHI

private static final double DEFAULT_PHI

See Also:

Constant Field Values

DEFAULT_EXPANSION_FACTOR

private static final int DEFAULT_EXPANSION_FACTOR

See Also:

Constant Field Values

DEFAULT_EXP_HISTOGRAM_EPSILON

private static final double DEFAULT_EXP_HISTOGRAM_EPSILON

See Also:

Constant Field Values

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 java.util.List<BarSplittingBiasedHistogram.Bar> bars

maxSizeTable

private final double[] maxSizeTable

size

private long size

Constructor Detail

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 Detail

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 java.lang.String toString()

Overrides:

toString in class java.lang.Object

getBuckets

public java.util.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

java.util.List<BarSplittingBiasedHistogram.Bar> bars()

alphaPhi

double alphaPhi()

phi

double phi()

bucketCount

int bucketCount()