Package cern.jet.stat.quantile

Class KnownDoubleQuantileEstimator

  • All Implemented Interfaces:
    DoubleQuantileFinder, java.io.Serializable, java.lang.Cloneable
    class KnownDoubleQuantileEstimator
extends DoubleQuantileEstimator
    Approximate quantile finding algorithm for known N requiring only one pass and little main memory; computes quantiles over a sequence of double elements.

    Needs as input the following parameters:

    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.

    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".

    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.

    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:
    QuantileFinderFactory, UnknownApproximateDoubleQuantileFinder

    • Field Detail

      • beta

        protected double beta

      • weHadMoreThanOneEmptyBuffer

        protected boolean weHadMoreThanOneEmptyBuffer

      • samplingRate

        protected double samplingRate

      • N

        protected long N

    • Constructor Detail

      • 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 buffers
        k - the number of elements per buffer
        N - 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 Detail

      • addInfinities

        protected void addInfinities​(int missingInfinities,
                             DoubleBuffer buffer)
        Parameters:
        infinities - the number of infinities to fill.
        buffer - the buffer into which the infinities shall be filled.

      • 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 interface DoubleQuantileFinder
        Overrides:
        clear in class DoubleQuantileEstimator

      • removeInfinitiesFrom

        protected void removeInfinitiesFrom​(int infinities,
                                    DoubleBuffer buffer)
        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.