Class UnknownDoubleQuantileEstimator

java.lang.Object

cern.colt.PersistentObject

cern.jet.stat.quantile.DoubleQuantileEstimator

cern.jet.stat.quantile.UnknownDoubleQuantileEstimator

All Implemented Interfaces:

DoubleQuantileFinder, Serializable, Cloneable

class UnknownDoubleQuantileEstimator
extends DoubleQuantileEstimator

Approximate quantile finding algorithm for unknown N requiring only one pass and little main memory; computes quantiles over a sequence of double elements. This algorithm requires at most two times the memory of a corresponding approx. quantile finder knowing N.

Needs as input the following parameters:

1. quantiles - the number of quantiles to be computed.

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

3. 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, Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets. Accepted for Proc. of the 1999 ACM SIGMOD Int. Conf. on Management of Data, Paper (soon) available here.

Version:

1.0, 09/24/99

See Also:

• QuantileFinderFactory
• invalid reference

  KnownApproximateDoubleQuantileFinder

Field Summary

Fields

Modifier and Type	Field	Description
protected int	currentTreeHeight
protected double	precomputeEpsilon
protected WeightedRandomSampler	sampler
protected final int	treeHeightStartingSampling

Fields inherited from class DoubleQuantileEstimator

bufferSet, currentBufferToFill, totalElementsFilled

Fields inherited from class PersistentObject

serialVersionUID

Constructor Summary

Constructors

Constructor	Description
UnknownDoubleQuantileEstimator(int b, int k, int h, double precomputeEpsilon, RandomEngine generator)	Constructs an approximate quantile finder with b buffers, each having k elements.

Method Summary

Modifier and Type	Method	Description
protected DoubleBuffer[]	buffersToCollapse()	Not yet commented.
void	clear()	Removes all elements from the receiver.
Object	clone()	Returns a deep copy of the receiver.
protected void	newBuffer()	Not yet commented.
protected void	postCollapse(DoubleBuffer[] toCollapse)	Not yet commented.
DoubleArrayList	quantileElements(DoubleArrayList phis)	Computes the specified quantile elements over the values previously added.
protected boolean	sampleNextElement()	Not yet commented.
protected static void	sortAscendingByLevel(DoubleBuffer[] fullBuffers)	To do.
String	toString()	Returns a String representation of the receiver.

Methods inherited from class DoubleQuantileEstimator

add, addAllOf, addAllOfFromTo, collapse, contains, forEach, memory, phi, preProcessPhis, setUp, size, totalMemory

Methods inherited from class Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

currentTreeHeight

protected int currentTreeHeight

treeHeightStartingSampling

protected final int treeHeightStartingSampling

sampler

protected WeightedRandomSampler sampler

precomputeEpsilon

protected double precomputeEpsilon

Constructor Details

UnknownDoubleQuantileEstimator

public UnknownDoubleQuantileEstimator(int b,
 int k,
 int h,
 double precomputeEpsilon,
 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

h - the tree height at which sampling shall start.

precomputeEpsilon - the epsilon for which quantiles shall be precomputed; set this value invalid input: '<'=0.0 if nothing shall be precomputed.

generator - a uniform random number generator.

Method Details

buffersToCollapse

protected DoubleBuffer[] buffersToCollapse()

Not yet commented.

Overrides:

buffersToCollapse in class DoubleQuantileEstimator

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

clone

public Object clone()

Returns a deep copy of the receiver.

Specified by:

clone in interface DoubleQuantileFinder

Overrides:

clone in class DoubleQuantileEstimator

Returns:

a deep copy of the receiver.

newBuffer

protected void newBuffer()

Not yet commented.

Specified by:

newBuffer in class DoubleQuantileEstimator

postCollapse

protected void postCollapse(DoubleBuffer[] toCollapse)

Not yet commented.

Specified by:

postCollapse in class DoubleQuantileEstimator

quantileElements

public DoubleArrayList quantileElements(DoubleArrayList phis)

Computes the specified quantile elements over the values previously added.

Specified by:

quantileElements in interface DoubleQuantileFinder

Overrides:

quantileElements in class DoubleQuantileEstimator

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.

sampleNextElement

protected boolean sampleNextElement()

Not yet commented.

Specified by:

sampleNextElement in class DoubleQuantileEstimator

sortAscendingByLevel

protected static void sortAscendingByLevel(DoubleBuffer[] fullBuffers)

To do. This could faster be done without sorting (min and second min).

toString

public String toString()

Returns a String representation of the receiver.

Overrides:

toString in class DoubleQuantileEstimator