Package org.terracotta.statistics.derived.histogram

Class ExponentialHistogram

java.lang.Object
org.terracotta.statistics.derived.histogram.ExponentialHistogram
public class ExponentialHistogram extends Object
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:

  • Field Summary

    Fields
    Modifier and Type
    Field
    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

    Constructors
    Modifier
    Constructor
    Description
    private
    ExponentialHistogram(double epsilon, int mergeThreshold, long window, int initialSize)
     
     
    ExponentialHistogram(double epsilon, long window)
    Creates an exponential histogram maintaining a count over window to within @{epsilon} fractional accuracy.

  • Method Summary

    Modifier and Type
    Method
    Description
    long
    count()
    Returns the approximate current count.
    private long[]
    doubleUp(long[] a)
     
    private void
    ensureCapacity(int logSize)
     
    double
    epsilon()
    Return the fractional accuracy of this exponential histogram
    long
    expire(long time)
    Expire old events.
    private void
    initializeArrays(int logMax)
     
    void
    insert(long time)
    Insert a single event at time
    void
    insert(long time, long count)
    Bulk insert count events at time.
    private static int[]
    lCanonical(int l, long count)
     
    private long[]
    makeBoxes(long time, long count)
     
    private int
    max_l(int logSize)
     
    private void
    merge(long[] bBoxes, long bTotal)
     
    private static long[]
    merge(long[] a, long[] b, int min, int max, long[] c)
     
    void
    merge(ExponentialHistogram b)
    Merge the supplied ExponentialHistogram in to this one.
    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)
     
    ExponentialHistogram
    split(double fraction)
    Split an exponential histogram off this one.
    private static int[]
    tailedLCanonical(int l, long count)
     
    String
    toString()
     
    private void
    transfer(long[] originalBoxes, long[] targetBoxes, int logSize, int count)
     

    Methods inherited from class java.lang.Object

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

  • Field Details

    • EMPTY_LONG_ARRAY

      private static final long[] EMPTY_LONG_ARRAY

    • epsilon

      private final double epsilon

    • mergeThreshold

      private final int mergeThreshold

    • window

      private final long window

    • boxes

      private long[] boxes

    • insert

      private int[] insert

    • total

      private long total

    • last

      private long last

  • Constructor Details

    • ExponentialHistogram

      public ExponentialHistogram(double epsilon, long window)
      Creates an exponential histogram maintaining a count over window to within @{epsilon} fractional accuracy.
      Parameters:
      epsilon - fractional accuracy
      window - sliding window size

    • ExponentialHistogram

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

  • Method Details

    • merge

      public void merge(ExponentialHistogram b)
      Merge the supplied ExponentialHistogram in to this one.
      Parameters:
      b - histogram to merge
      Throws:
      IllegalArgumentException - if the two merge-thresholds are not equals

    • merge

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

    • insert

      public void insert(long time, long count) throws IllegalArgumentException
      Bulk insert count events at time.
      Parameters:
      time - event time
      count - event count
      Throws:
      IllegalArgumentException - if count is negative

    • makeBoxes

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

    • tailedLCanonical

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

    • lCanonical

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

    • merge

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

    • insert

      public void insert(long time)
      Insert a single event at time
      Parameters:
      time - event timestamp

    • expire

      public long expire(long time)
      Expire old events.
      Parameters:
      time - current timestamp
      Returns:
      the count following expiry

    • min_l

      private int min_l(int logSize)

    • max_l

      private int max_l(int logSize)

    • count

      public long count()
      Returns the approximate current count.
      Returns:
      the approximate count

    • split

      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 - splitting fraction
      Returns:
      the new histogram

    • transfer

      private void transfer(long[] originalBoxes, long[] targetBoxes, int logSize, int count)

    • pull

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

    • doubleUp

      private long[] doubleUp(long[] a)

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • reverseSort

      private static int reverseSort(long[] a)

    • reverseSort

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

    • ensureCapacity

      private void ensureCapacity(int logSize)

    • initializeArrays

      private void initializeArrays(int logMax)

    • epsilon

      public double epsilon()
      Return the fractional accuracy of this exponential histogram
      Returns:
      fractional accuracy