Top Description Fields Constructors Methods
org.terracotta.statistics.derived.histogram

public Class ExponentialHistogram

extends Object
Class Inheritance
Imports
java.util.Arrays
An implementation of the Exponential Histogram sketch as outlined by Datar et al.

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

See Also
Maintaining Stream Statistics over Sliding Windows

Field Summary

Modifier and TypeField and Description
private long[]
boxes

private static final long[]
EMPTY_LONG_ARRAY

private final double
epsilon

private int[]
insert

private long
last

private final int
mergeThreshold

private long
total

private final long
window

Constructor Summary

AccessConstructor and Description
public
ExponentialHistogram(double
fractional accuracy
epsilon, long
sliding window size
window)

Creates an exponential histogram maintaining a count over window to within @{epsilon} fractional accuracy.

private
ExponentialHistogram(double epsilon, int mergeThreshold, long window, int initialSize)

Method Summary

Modifier and TypeMethod and Description
public long

Returns:

the approximate count
count()

Returns the approximate current count.

private long[]
doubleUp(long[] a)

private void
ensureCapacity(int logSize)

public double

Returns:

fractional accuracy
epsilon()

Return the fractional accuracy of this exponential histogram

public long

Returns:

the count following expiry
expire(long
current timestamp
time)

Expire old events.

private void
initializeArrays(int logMax)

public void
insert(long
event time
time, long
event count
count)

Bulk insert count events at time.

public void
insert(long
event timestamp
time)

Insert a single event at time

private static int[]
lCanonical(int l, long count)

private long[]
makeBoxes(long time, long count)

private int
max_l(int logSize)

public void
merge(ExponentialHistogram
histogram to merge
b)

Merge the supplied ExponentialHistogram in to this one.

private void
merge(long[] bBoxes, long bTotal)

private static long[]
merge(long[] a, long[] b, int min, int max, long[] c)

private int
min_l(int logSize)

private long[]
pull(long[] originalBoxes, int logSize, int count)

private static int
reverseSort(long[] a)

private static int
reverseSort(long[] a, int fromIndex, int toIndex)

public ExponentialHistogram

Returns:

the new histogram
split(double
splitting fraction
fraction)

Split an exponential histogram off this one.

private static int[]
tailedLCanonical(int l, long count)

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.
private void
transfer(long[] originalBoxes, long[] targetBoxes, int logSize, int count)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAllwaitwaitwait

Field Detail

boxesback to summary
private long[] boxes
EMPTY_LONG_ARRAYback to summary
private static final long[] EMPTY_LONG_ARRAY
epsilonback to summary
private final double epsilon
insertback to summary
private int[] insert
lastback to summary
private long last
mergeThresholdback to summary
private final int mergeThreshold
totalback to summary
private long total
windowback to summary
private final long window

Constructor Detail

ExponentialHistogramback to summary
public ExponentialHistogram(double epsilon, long window)

Creates an exponential histogram maintaining a count over window to within @{epsilon} fractional accuracy.

Parameters
epsilon:double

fractional accuracy

window:long

sliding window size

ExponentialHistogramback to summary
private ExponentialHistogram(double epsilon, int mergeThreshold, long window, int initialSize)

Method Detail

countback to summary
public long count()

Returns the approximate current count.

Returns:long

the approximate count

doubleUpback to summary
private long[] doubleUp(long[] a)
ensureCapacityback to summary
private void ensureCapacity(int logSize)
epsilonback to summary
public double epsilon()

Return the fractional accuracy of this exponential histogram

Returns:double

fractional accuracy

expireback to summary
public long expire(long time)

Expire old events.

Parameters
time:long

current timestamp

Returns:long

the count following expiry

initializeArraysback to summary
private void initializeArrays(int logMax)
insertback to summary
public void insert(long time, long count) throws IllegalArgumentException

Bulk insert count events at time.

Parameters
time:long

event time

count:long

event count

Exceptions
IllegalArgumentException:
if count is negative
insertback to summary
public void insert(long time)

Insert a single event at time

Parameters
time:long

event timestamp

lCanonicalback to summary
private static int[] lCanonical(int l, long count)
makeBoxesback to summary
private long[] makeBoxes(long time, long count)
max_lback to summary
private int max_l(int logSize)
mergeback to summary
public void merge(ExponentialHistogram b)

Merge the supplied ExponentialHistogram in to this one.

Parameters
b:ExponentialHistogram

histogram to merge

Exceptions
IllegalArgumentException:
if the two merge-thresholds are not equals
mergeback to summary
private void merge(long[] bBoxes, long bTotal)
mergeback to summary
private static long[] merge(long[] a, long[] b, int min, int max, long[] c)
min_lback to summary
private int min_l(int logSize)
pullback to summary
private long[] pull(long[] originalBoxes, int logSize, int count)
reverseSortback to summary
private static int reverseSort(long[] a)
reverseSortback to summary
private static int reverseSort(long[] a, int fromIndex, int toIndex)
splitback to summary
public ExponentialHistogram split(double fraction)

Split an exponential histogram off this one.

The returned histogram will contain {code fraction} of the events in this one.

Parameters
fraction:double

splitting fraction

Returns:ExponentialHistogram

the new histogram

tailedLCanonicalback to summary
private static int[] tailedLCanonical(int l, long count)
toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object.

Returns:String

a string representation of the object.

Annotations
@Override
transferback to summary
private void transfer(long[] originalBoxes, long[] targetBoxes, int logSize, int count)