Class CKMSQuantiles


  • final class CKMSQuantiles
    extends java.lang.Object
    Algorithm solving the "Targeted Quantile Problem" as described in "Effective Computation of Biased Quantiles over Data Streams" by Cormode, Korn, Muthukrishnan, and Srivastava.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private double[] buffer
      Note that the buffer size could as well be less than the compressInterval.
      private int bufferPos  
      private int compressInterval
      Compress is called every compressInterval inserts.
      private int insertsSinceLastCompress  
      (package private) int n
      Total number of observations (not including those that are still in the buffer).
      (package private) CKMSQuantiles.Quantile[] quantiles  
      (package private) java.util.LinkedList<CKMSQuantiles.Sample> samples
      List of sampled observations, ordered by Sample.value.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) void compress()
      Merge pairs of consecutive samples if this doesn't violate the error function.
      (package private) int f​(int r)
      Error function, as in definition 5 of the paper.
      private void flush()  
      double get​(double q)
      Get the estimated value at the specified quantile.
      void insert​(double value)
      Add an observed value
      (package private) void insertBatch​(double[] sortedBuffer, int toIndex)
      Inserts the elements from index 0 to index toIndex from the sortedBuffer.
      private void insertBefore​(java.util.ListIterator<CKMSQuantiles.Sample> iterator, double value, int r)  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • n

        int n
        Total number of observations (not including those that are still in the buffer).
      • samples

        final java.util.LinkedList<CKMSQuantiles.Sample> samples
        List of sampled observations, ordered by Sample.value.
      • compressInterval

        private final int compressInterval
        Compress is called every compressInterval inserts. Note that the buffer is flushed whenever get() is called, so we cannot just wait until the buffer is full before we call compress.
        See Also:
        Constant Field Values
      • insertsSinceLastCompress

        private int insertsSinceLastCompress
      • buffer

        private final double[] buffer
        Note that the buffer size could as well be less than the compressInterval. However, the buffer size should not be greater than the compressInterval, because the compressInterval is not respected in flush(), so if you want to compress more often than calling flush() that won't work.
      • bufferPos

        private int bufferPos
    • Method Detail

      • insert

        public void insert​(double value)
        Add an observed value
      • flush

        private void flush()
      • insertBatch

        void insertBatch​(double[] sortedBuffer,
                         int toIndex)
        Inserts the elements from index 0 to index toIndex from the sortedBuffer.
      • insertBefore

        private void insertBefore​(java.util.ListIterator<CKMSQuantiles.Sample> iterator,
                                  double value,
                                  int r)
      • get

        public double get​(double q)
        Get the estimated value at the specified quantile.
      • f

        int f​(int r)
        Error function, as in definition 5 of the paper.
      • compress

        void compress()
        Merge pairs of consecutive samples if this doesn't violate the error function.