Package org.terracotta.statistics.derived.histogram

Class ExponentialHistogram

  • public class ExponentialHistogram
extends java.lang.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:
    Maintaining Stream Statistics over Sliding Windows

    • 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

      All Methods Static Methods Instance Methods Concrete Methods 
      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)  
      java.lang.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 Detail

      • 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 Detail

      • 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 Detail

      • merge

        public void merge​(ExponentialHistogram b)
        Merge the supplied ExponentialHistogram in to this one.
        Parameters:
        b - histogram to merge
        Throws:
        java.lang.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 java.lang.IllegalArgumentException
        Bulk insert count events at time.
        Parameters:
        time - event time
        count - event count
        Throws:
        java.lang.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 java.lang.String toString()
        Overrides:
        toString in class java.lang.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