Package io.prometheus.client
Class CKMSQuantiles
java.lang.Object
io.prometheus.client.CKMSQuantiles
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 ClassesModifier and TypeClassDescription(package private) static class
(package private) static class
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate final double[]
Note that the buffer size could as well be less than the compressInterval.private int
private final int
Compress is called every compressInterval inserts.private int
(package private) int
Total number of observations (not including those that are still in the buffer).(package private) final CKMSQuantiles.Quantile[]
(package private) final LinkedList
<CKMSQuantiles.Sample> List of sampled observations, ordered by Sample.value. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescription(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
(ListIterator<CKMSQuantiles.Sample> iterator, double value, int r)
-
Field Details
-
quantiles
-
n
int nTotal 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 compressIntervalCompress 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[] bufferNote 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
-
CKMSQuantiles
-
-
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
-
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.
-