Class CKMSQuantiles

java.lang.Object
io.prometheus.client.CKMSQuantiles

final class CKMSQuantiles extends 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 Details

    • quantiles

      final CKMSQuantiles.Quantile[] quantiles
    • n

      int n
      Total number of observations (not including those that are still in the buffer).
    • 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:
    • 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
  • Constructor Details

  • Method Details

    • 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(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.