Package io.prometheus.client
Class CKMSQuantiles
- java.lang.Object
-
- io.prometheus.client.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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description (package private) static class
CKMSQuantiles.Quantile
(package private) static class
CKMSQuantiles.Sample
-
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.
-
Constructor Summary
Constructors Constructor Description CKMSQuantiles(CKMSQuantiles.Quantile... quantiles)
-
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)
-
-
-
Field Detail
-
quantiles
final CKMSQuantiles.Quantile[] quantiles
-
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
-
-
Constructor Detail
-
CKMSQuantiles
public CKMSQuantiles(CKMSQuantiles.Quantile... quantiles)
-
-
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.
-
-