Package cern.jet.stat.quantile
Class KnownDoubleQuantileEstimator
java.lang.Object
cern.colt.PersistentObject
cern.jet.stat.quantile.DoubleQuantileEstimator
cern.jet.stat.quantile.KnownDoubleQuantileEstimator
- All Implemented Interfaces:
DoubleQuantileFinder
,Serializable
,Cloneable
Approximate quantile finding algorithm for known N requiring only one pass and little main memory; computes quantiles over a sequence of double elements.
1. N - the number of values of the data sequence over which quantiles are to be determined.
2. quantiles - the number of quantiles to be computed.
3. epsilon - the allowed approximation error on quantiles. The approximation guarantee of this algorithm is explicit.
4. delta - the probability allowed that the approximation error fails to be smaller than epsilon. Set delta to zero for explicit non probabilistic guarantees.
You usually don't instantiate quantile finders by using the constructor. Instead use the factory QuantileFinderFactor to do so. It will set up the right parametrization for you.
Needs as input the following parameters:
It is also possible to couple the approximation algorithm with random sampling to further reduce memory requirements. With sampling, the approximation guarantees are explicit but probabilistic, i.e. they apply with respect to a (user controlled) confidence parameter "delta".
After Gurmeet Singh Manku, Sridhar Rajagopalan and Bruce G. Lindsay, Approximate Medians and other Quantiles in One Pass and with Limited Memory, Proc. of the 1998 ACM SIGMOD Int. Conf. on Management of Data, Paper available here.
- Version:
- 1.0, 09/24/99
- See Also:
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected double
protected long
protected RandomSamplingAssistant
protected double
protected boolean
Fields inherited from class cern.jet.stat.quantile.DoubleQuantileEstimator
bufferSet, currentBufferToFill, totalElementsFilled
Fields inherited from class cern.colt.PersistentObject
serialVersionUID
-
Constructor Summary
ConstructorsConstructorDescriptionKnownDoubleQuantileEstimator
(int b, int k, long N, double samplingRate, RandomEngine generator) Constructs an approximate quantile finder with b buffers, each having k elements. -
Method Summary
Modifier and TypeMethodDescriptionprotected void
addInfinities
(int missingInfinities, DoubleBuffer buffer) protected DoubleBuffer[]
Not yet commented.void
clear()
Removes all elements from the receiver.clone()
Returns a deep copy of the receiver.protected void
Not yet commented.protected void
postCollapse
(DoubleBuffer[] toCollapse) Not yet commented.protected DoubleArrayList
Default implementation does nothing.Computes the specified quantile elements over the values previously added.protected void
removeInfinitiesFrom
(int infinities, DoubleBuffer buffer) Reading off quantiles requires to fill some +infinity, -infinity values to make a partial buffer become full.protected boolean
Not yet commented.Methods inherited from class cern.jet.stat.quantile.DoubleQuantileEstimator
add, addAllOf, addAllOfFromTo, collapse, contains, forEach, memory, phi, setUp, size, toString, totalMemory
-
Field Details
-
beta
protected double beta -
weHadMoreThanOneEmptyBuffer
protected boolean weHadMoreThanOneEmptyBuffer -
samplingAssistant
-
samplingRate
protected double samplingRate -
N
protected long N
-
-
Constructor Details
-
KnownDoubleQuantileEstimator
public KnownDoubleQuantileEstimator(int b, int k, long N, double samplingRate, RandomEngine generator) Constructs an approximate quantile finder with b buffers, each having k elements.- Parameters:
b
- the number of buffersk
- the number of elements per bufferN
- the total number of elements over which quantiles are to be computed.samplingRate
- 1.0 --> all elements are consumed. 10.0 --> Consumes one random element from successive blocks of 10 elements each. Etc.generator
- a uniform random number generator.
-
-
Method Details
-
addInfinities
- Parameters:
buffer
- the buffer into which the infinities shall be filled.infinities
- the number of infinities to fill.
-
buffersToCollapse
Not yet commented.- Overrides:
buffersToCollapse
in classDoubleQuantileEstimator
-
clear
public void clear()Removes all elements from the receiver. The receiver will be empty after this call returns, and its memory requirements will be close to zero.- Specified by:
clear
in interfaceDoubleQuantileFinder
- Overrides:
clear
in classDoubleQuantileEstimator
-
clone
Returns a deep copy of the receiver.- Specified by:
clone
in interfaceDoubleQuantileFinder
- Overrides:
clone
in classDoubleQuantileEstimator
- Returns:
- a deep copy of the receiver.
-
newBuffer
protected void newBuffer()Not yet commented.- Specified by:
newBuffer
in classDoubleQuantileEstimator
-
postCollapse
Not yet commented.- Specified by:
postCollapse
in classDoubleQuantileEstimator
-
preProcessPhis
Description copied from class:DoubleQuantileEstimator
Default implementation does nothing.- Overrides:
preProcessPhis
in classDoubleQuantileEstimator
-
quantileElements
Computes the specified quantile elements over the values previously added.- Specified by:
quantileElements
in interfaceDoubleQuantileFinder
- Overrides:
quantileElements
in classDoubleQuantileEstimator
- Parameters:
phis
- the quantiles for which elements are to be computed. Each phi must be in the interval [0.0,1.0]. phis must be sorted ascending.- Returns:
- the approximate quantile elements.
-
removeInfinitiesFrom
Reading off quantiles requires to fill some +infinity, -infinity values to make a partial buffer become full. This method removes the infinities which were previously temporarily added to a partial buffer. Removing them is necessary if we want to continue filling more elements. Precondition: the buffer is sorted ascending.- Parameters:
infinities
- the number of infinities previously filled.buffer
- the buffer into which the infinities were filled.
-
sampleNextElement
protected boolean sampleNextElement()Not yet commented.- Specified by:
sampleNextElement
in classDoubleQuantileEstimator
-