build/colt/doc/api/hep/aida/bin/QuantileBin1D.html (a20104a) - Rabbit simulation · Portfolio Code

QuantileBin1D.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">

<HTML>
<HEAD>

<TITLE>
QuantileBin1D (Colt 1.2.0 - API Specification)
</TITLE>

<SCRIPT type="text/javascript">
function windowTitle()
{
 parent.document.title="QuantileBin1D (Colt 1.2.0 - API Specification)";
}
</SCRIPT>

</HEAD>

<A NAME="navbar_top"></A>
<A HREF="#skip-navbar_top" title="Skip navigation links"></A>
<TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY="">
<TR>
<TD COLSPAN=3 BGCOLOR="#EEEEFF" CLASS="NavBarCell1">
<A NAME="navbar_top_firstrow"></A>
<TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY="">
 <TR ALIGN="center" VALIGN="top">
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../overview-summary.html">Overview</A>&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-summary.html">Package</A>&nbsp;</TD>
 <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> &nbsp;Class&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="class-use/QuantileBin1D.html">Use</A>&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-tree.html">Tree</A>&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../deprecated-list.html">Deprecated</A>&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../index-files/index-1.html">Index</A>&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../help-doc.html">Help</A>&nbsp;</TD>
 </TR>
</TABLE>
</TD>
<TD ALIGN="right" VALIGN="top" ROWSPAN=3>
Colt 1.2.0
</TD>
</TR>

<TR>
<TD BGCOLOR="white" CLASS="NavBarCell2">
&nbsp;<A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">PREV CLASS</A>&nbsp;
&nbsp;<A HREF="../../../hep/aida/bin/StaticBin1D.html" title="class in hep.aida.bin">NEXT CLASS</A></TD>
<TD BGCOLOR="white" CLASS="NavBarCell2">
 <A HREF="../../../index.html" target="_top">FRAMES</A> &nbsp;
&nbsp;<A HREF="QuantileBin1D.html" target="_top">NO FRAMES</A> &nbsp;
&nbsp;<SCRIPT type="text/javascript">
 
</SCRIPT>
<NOSCRIPT>
 <A HREF="../../../allclasses-noframe.html">All Classes</A>
</NOSCRIPT>

</TD>
</TR>
<TR>
<TD VALIGN="top" CLASS="NavBarCell3">
 SUMMARY:&nbsp;NESTED&nbsp;|&nbsp;<A HREF="#fields_inherited_from_class_cern.colt.PersistentObject">FIELD</A>&nbsp;|&nbsp;<A HREF="#constructor_summary">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_summary">METHOD</A></TD>
<TD VALIGN="top" CLASS="NavBarCell3">
DETAIL:&nbsp;FIELD&nbsp;|&nbsp;<A HREF="#constructor_detail">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_detail">METHOD</A></TD>
</TR>
</TABLE>
<A NAME="skip-navbar_top"></A>

<HR>

<H2>

hep.aida.bin
 
Class QuantileBin1D</H2>
<PRE>
<A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html" title="class or interface in java.lang">java.lang.Object</A>
 <IMG SRC="../../../resources/inherit.gif" ALT="extended by"><A HREF="../../../cern/colt/PersistentObject.html" title="class in cern.colt">cern.colt.PersistentObject</A>
 <IMG SRC="../../../resources/inherit.gif" ALT="extended by"><A HREF="../../../hep/aida/bin/AbstractBin.html" title="class in hep.aida.bin">hep.aida.bin.AbstractBin</A>
 <IMG SRC="../../../resources/inherit.gif" ALT="extended by"><A HREF="../../../hep/aida/bin/AbstractBin1D.html" title="class in hep.aida.bin">hep.aida.bin.AbstractBin1D</A>
 <IMG SRC="../../../resources/inherit.gif" ALT="extended by"><A HREF="../../../hep/aida/bin/StaticBin1D.html" title="class in hep.aida.bin">hep.aida.bin.StaticBin1D</A>
 <IMG SRC="../../../resources/inherit.gif" ALT="extended by"><A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">hep.aida.bin.MightyStaticBin1D</A>
 <IMG SRC="../../../resources/inherit.gif" ALT="extended by">hep.aida.bin.QuantileBin1D
</PRE>
<DL>
<DT>All Implemented Interfaces: <DD><A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Cloneable.html" title="class or interface in java.lang">Cloneable</A>, <A HREF="../../../cern/colt/buffer/DoubleBufferConsumer.html" title="interface in cern.colt.buffer">DoubleBufferConsumer</A>, <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/io/Serializable.html" title="class or interface in java.io">Serializable</A></DD>
</DL>
<DL>
<DT>Direct Known Subclasses: <DD><A HREF="../../../hep/aida/bin/DynamicBin1D.html" title="class in hep.aida.bin">DynamicBin1D</A></DD>
</DL>
<HR>
<DL>
<DT>public class QuantileBin1D<DT>extends <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">MightyStaticBin1D</A></DL>

1-dimensional non-rebinnable bin holding <tt>double</tt> elements with scalable quantile operations defined upon;
Using little main memory, quickly computes approximate quantiles over very large data sequences with and even without a-priori knowledge of the number of elements to be filled;
Conceptually a strongly lossily compressed multiset (or bag);
Guarantees to respect the worst case approximation error specified upon instance construction.
First see the <a href="package-summary.html">package summary</a> and javadoc <a href="package-tree.html">tree view</a> to get the broad picture.

Motivation and Problem:
Intended to help scale applications requiring quantile computation.
Quantile computation on very large data sequences is problematic, for the following reasons:
Computing quantiles requires sorting the data sequence.
To sort a data sequence the entire data sequence needs to be available.
Thus, data cannot be thrown away during filling (as done by static bins like <A HREF="../../../hep/aida/bin/StaticBin1D.html" title="class in hep.aida.bin"><CODE>StaticBin1D</CODE></A> and <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin"><CODE>MightyStaticBin1D</CODE></A>).
It needs to be kept, either in main memory or on disk.
There is often not enough main memory available.
Thus, during filling data needs to be streamed onto disk.
Sorting disk resident data is prohibitively time consuming.
As a consequence, traditional methods either need very large memories (like <A HREF="../../../hep/aida/bin/DynamicBin1D.html" title="class in hep.aida.bin"><CODE>DynamicBin1D</CODE></A>) or time consuming disk based sorting.

This class proposes to efficiently solve the problem, at the expense of producing approximate rather than exact results.
It can deal with infinitely many elements without resorting to disk.
The main memory requirements are smaller than for any other known approximate technique by an order of magnitude.
They get even smaller if an upper limit on the maximum number of elements ever to be added is known a-priori.

Approximation error:
The approximation guarantees are parametrizable and explicit but probabilistic, and apply for arbitrary value distributions and arrival distributions of the data sequence.
In other words, this class guarantees to respect the worst case approximation error specified upon instance construction to a certain probability.
Of course, if it is specified that the approximation error should not exceed some number very close to zero,
this class will potentially consume just as much memory as any of the traditional exact techniques would do.
However, for errors larger than 10-5, its memory requirements are modest, as shown by the table below.

Main memory requirements:
Given in megabytes, assuming a single element (<tt>double</tt>) takes 8 byte.
The number of elements required is then <tt>MB*1024*1024/8</tt>.

Parameters:
<ul>
<li>epsilon - the maximum allowed approximation error on quantiles; in <tt>[0.0,1.0]</tt>.
To get exact rather than approximate quantiles, set <tt>epsilon=0.0</tt>;

<li>delta - the probability allowed that the approximation error fails to be smaller than epsilon; in <tt>[0.0,1.0]</tt>.
To avoid probabilistic answers, set <tt>delta=0.0</tt>.
For example, <tt>delta = 0.0001</tt> is equivalent to a confidence of <tt>99.99%</tt>.

<li>quantiles - the number of quantiles to be computed; in <tt>[0,Integer.MAX_VALUE]</tt>.

<li>is N known? - specifies whether the exact size of the dataset over which quantiles are to be computed is known.

<li>Nmax - the exact dataset size, if known. Otherwise, an upper limit on the dataset size. If no upper limit is known set to infinity (<tt>Long.MAX_VALUE</tt>).
</ul>
 Nmax=inf - we are sure that exactly (known) or less than (unknown) infinity elements will be added.
 Nmax=106 - we are sure that exactly (known) or less than (unknown) 106 elements will be added.
 Nmax=107 - we are sure that exactly (known) or less than (unknown) 107 elements will be added.
 Nmax=108 - we are sure that exactly (known) or less than (unknown) 108 elements will be added.

<table width="75%" border="1" cellpadding="6" cellspacing="0" align="center">
 <tr align="center" valign="middle"> 
 <td width="20%" nowrap colspan="13" bgcolor="#33CC66"> 
 <div align="center">Required main memory 
 [MB]</div>
 </td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="7%" nowrap rowspan="2" bgcolor="#FF9966">#quantiles</td>
 <td width="6%" nowrap rowspan="2" bgcolor="#FF9966"> 
 <div align="center"></div>
 <div align="center"></div>
 <div align="center">epsilon</div>
 </td>
 <td width="6%" nowrap rowspan="2" bgcolor="#FF9966">delta</td>
 <td width="1%" nowrap rowspan="31">&nbsp;</td>
 <td nowrap colspan="4" bgcolor="#FF9966">N unknown</td>
 <td width="1%" nowrap align="center" valign="middle" bgcolor="#C0C0C0" rowspan="31"></td>
 <td nowrap colspan="4" bgcolor="#FF9966">N known</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="7%" nowrap bgcolor="#FF9966">Nmax=inf</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=106</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=107</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=108</td>
 <td width="8%" nowrap bgcolor="#FF9966">Nmax=inf</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=106</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=107</td>
 <td width="19%" nowrap bgcolor="#FF9966">Nmax=108</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td nowrap bgcolor="#C0C0C0" colspan="3"> 
 <div align="center"></div>
 </td>
 <td nowrap colspan="4">&nbsp;</td>
 <td nowrap colspan="4">&nbsp;</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="7%" nowrap bgcolor="#FFCCCC">any</td>
 <td width="6%" nowrap bgcolor="#FFCCCC"> 
 <div align="center">0</div>
 </td>
 <td width="6%" nowrap bgcolor="#FFCCCC">any</td>
 <td width="7%" nowrap bgcolor="#66CCFF">infinity</td>
 <td width="9%" nowrap bgcolor="#66CCFF">7.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">76</td>
 <td width="9%" nowrap bgcolor="#66CCFF">762</td>
 <td width="8%" nowrap bgcolor="#66CCFF">infinity</td>
 <td width="9%" nowrap bgcolor="#66CCFF">7.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">76</td>
 <td width="19%" nowrap bgcolor="#66CCFF">762</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="7%" nowrap rowspan="6" bgcolor="#FFCCCC">any</td>
 <td width="6%" nowrap bgcolor="#FFCCCC"> 
 <div align="center">10 -1</div>
 </td>
 <td width="6%" nowrap rowspan="6" bgcolor="#FFCCCC">0</td>
 <td width="7%" nowrap rowspan="6" bgcolor="#66CCFF">infinity</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.003</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.005</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.006</td>
 <td width="8%" nowrap bgcolor="#66CCFF">0.03</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.003</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.005</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.006</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap bgcolor="#FFCCCC"> 
 <div align="center">10 -2</div>
 </td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.02</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.03</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.05</td>
 <td width="8%" nowrap bgcolor="#66CCFF">0.31</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.02</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.03</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.05</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap bgcolor="#FFCCCC"> 
 <div align="center">10 -3</div>
 </td>
 <td width="9%" nowrap align="center" valign="middle" bgcolor="#66CCFF">0.12</td>
 <td width="9%" nowrap align="center" valign="middle" bgcolor="#66CCFF">0.2</td>
 <td width="9%" nowrap align="center" valign="middle" bgcolor="#66CCFF">0.3</td>
 <td width="8%" nowrap bgcolor="#66CCFF">2.7</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.12</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.2</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.3</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap bgcolor="#FFCCCC"> 
 <div align="center">10 -4</div>
 </td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">1.2</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.1</td>
 <td width="8%" nowrap bgcolor="#66CCFF">26.9</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">1.2</td>
 <td width="19%" nowrap bgcolor="#66CCFF">2.1</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap bgcolor="#FFCCCC"> 
 <div align="center">10 -5</div>
 </td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">6.4</td>
 <td width="9%" nowrap bgcolor="#66CCFF">11.6</td>
 <td width="8%" nowrap bgcolor="#66CCFF">205</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">6.4</td>
 <td width="19%" nowrap bgcolor="#66CCFF">11.6</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap bgcolor="#FFCCCC"> 
 <div align="center">10 -6</div>
 </td>
 <td width="9%" nowrap bgcolor="#66CCFF">7.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">25.4</td>
 <td width="9%" nowrap bgcolor="#66CCFF">63.6</td>
 <td width="8%" nowrap bgcolor="#66CCFF">1758</td>
 <td width="9%" nowrap bgcolor="#66CCFF">7.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">25.4</td>
 <td width="19%" nowrap bgcolor="#66CCFF">63.6</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td nowrap bgcolor="#C0C0C0" colspan="3"></td>
 <td nowrap colspan="4">&nbsp;</td>
 <td nowrap colspan="4">&nbsp;</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="7%" nowrap bgcolor="#FFCCCC" rowspan="8">100</td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC" rowspan="2"> 
 <div align="center">10 -2</div>
 </td>
 <td width="6%" nowrap bgcolor="#FFCCCC">10 -1</td>
 <td width="7%" nowrap bgcolor="#66CCFF">0.033</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.021</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.03</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.03</td>
 <td width="8%" nowrap bgcolor="#66CCFF">0.020</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.020</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.020</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.020</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap bgcolor="#FFCCCC">10 -5</td>
 <td width="7%" nowrap bgcolor="#66CCFF">0.038</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.021</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.03</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.04</td>
 <td width="8%" nowrap bgcolor="#66CCFF">0.024</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.020</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.020</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.020</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC" rowspan="2"> 
 <div align="center">10 -3</div>
 </td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -1</td>
 <td width="7%" nowrap bgcolor="#66CCFF">0.48</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.12</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.2</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.3</td>
 <td width="8%" nowrap bgcolor="#66CCFF">0.32</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.12</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.2</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.3</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -5</td>
 <td width="7%" nowrap bgcolor="#66CCFF">0.54</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.12</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.2</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.3</td>
 <td width="8%" nowrap bgcolor="#66CCFF">0.37</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.12</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.2</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.3</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC" rowspan="2"> 
 <div align="center">10 -4</div>
 </td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -1</td>
 <td width="7%" nowrap bgcolor="#66CCFF">6.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">1.2</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.1</td>
 <td width="8%" nowrap bgcolor="#66CCFF">4.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">1.2</td>
 <td width="19%" nowrap bgcolor="#66CCFF">2.1</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -5</td>
 <td width="7%" nowrap bgcolor="#66CCFF">7.2</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">1.2</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.1</td>
 <td width="8%" nowrap bgcolor="#66CCFF">5.2</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.6</td>
 <td width="9%" nowrap bgcolor="#66CCFF">1.2</td>
 <td width="19%" nowrap bgcolor="#66CCFF">2.1</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC" rowspan="2"> 
 <div align="center">10 -5</div>
 </td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -1</td>
 <td width="7%" nowrap bgcolor="#66CCFF">86</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">6.4</td>
 <td width="9%" nowrap bgcolor="#66CCFF">11.6</td>
 <td width="8%" nowrap bgcolor="#66CCFF">63</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">6.4</td>
 <td width="19%" nowrap bgcolor="#66CCFF">11.6</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -5</td>
 <td width="7%" nowrap bgcolor="#66CCFF">94</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">6.4</td>
 <td width="9%" nowrap bgcolor="#66CCFF">11.6</td>
 <td width="8%" nowrap bgcolor="#66CCFF">70</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">6.4</td>
 <td width="19%" nowrap bgcolor="#66CCFF">11.6</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td nowrap bgcolor="#C0C0C0" colspan="3"></td>
 <td nowrap colspan="4">&nbsp;</td>
 <td nowrap colspan="4">&nbsp;</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="7%" nowrap align="center" valign="middle" bgcolor="#FFCCCC" rowspan="8">10000</td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC" rowspan="2"> 
 <div align="center">10 -2</div>
 </td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -1</td>
 <td width="7%" nowrap bgcolor="#66CCFF">0.04</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.02</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.03</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.04</td>
 <td width="8%" nowrap bgcolor="#66CCFF">0.02</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.02</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.02</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.02</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -5</td>
 <td width="7%" nowrap bgcolor="#66CCFF">0.04</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.02</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.03</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.04</td>
 <td width="8%" nowrap bgcolor="#66CCFF">0.03</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.02</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.03</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.03</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC" rowspan="2"> 
 <div align="center">10 -3</div>
 </td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -1</td>
 <td width="7%" nowrap bgcolor="#66CCFF">0.52</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.12</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.21</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.3</td>
 <td width="8%" nowrap bgcolor="#66CCFF">0.35</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.12</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.21</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.3</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -5</td>
 <td width="7%" nowrap bgcolor="#66CCFF">0.56</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.12</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.21</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.3</td>
 <td width="8%" nowrap bgcolor="#66CCFF">0.38</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.12</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.21</td>
 <td width="19%" nowrap bgcolor="#66CCFF">0.3</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC" rowspan="2"> 
 <div align="center">10 -4</div>
 </td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -1</td>
 <td width="7%" nowrap bgcolor="#66CCFF">7.0</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.64</td>
 <td width="9%" nowrap bgcolor="#66CCFF">1.2</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.1</td>
 <td width="8%" nowrap bgcolor="#66CCFF">5.0</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.64</td>
 <td width="9%" nowrap bgcolor="#66CCFF">1.2</td>
 <td width="19%" nowrap bgcolor="#66CCFF">2.1</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -5</td>
 <td width="7%" nowrap bgcolor="#66CCFF">7.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.64</td>
 <td width="9%" nowrap bgcolor="#66CCFF">1.2</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.1</td>
 <td width="8%" nowrap bgcolor="#66CCFF">5.4</td>
 <td width="9%" nowrap bgcolor="#66CCFF">0.64</td>
 <td width="9%" nowrap bgcolor="#66CCFF">1.2</td>
 <td width="19%" nowrap bgcolor="#66CCFF">2.1</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC" rowspan="2"> 
 <div align="center">10 -5</div>
 </td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -1</td>
 <td width="7%" nowrap bgcolor="#66CCFF">90</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">6.4</td>
 <td width="9%" nowrap bgcolor="#66CCFF">11.6</td>
 <td width="8%" nowrap bgcolor="#66CCFF">67</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">6.4</td>
 <td width="19%" nowrap bgcolor="#66CCFF">11.6</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FFCCCC">10 -5</td>
 <td width="7%" nowrap bgcolor="#66CCFF">96</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">6.4</td>
 <td width="9%" nowrap bgcolor="#66CCFF">11.6</td>
 <td width="8%" nowrap bgcolor="#66CCFF">71</td>
 <td width="9%" nowrap bgcolor="#66CCFF">2.5</td>
 <td width="9%" nowrap bgcolor="#66CCFF">6.4</td>
 <td width="19%" nowrap bgcolor="#66CCFF">11.6</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="19%" nowrap align="center" valign="middle" colspan="3">&nbsp;</td>
 <td width="34%" nowrap colspan="4">&nbsp;</td>
 <td width="45%" nowrap colspan="4">&nbsp;</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="7%" nowrap align="center" valign="middle" bgcolor="#FF9966" rowspan="2">#quantiles</td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FF9966" rowspan="2">epsilon</td>
 <td width="6%" nowrap align="center" valign="middle" bgcolor="#FF9966" rowspan="2">delta</td>
 <td width="7%" nowrap bgcolor="#FF9966">Nmax=inf</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=106</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=107</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=108</td>
 <td width="7%" nowrap bgcolor="#FF9966">Nmax=inf</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=106</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=107</td>
 <td width="9%" nowrap bgcolor="#FF9966">Nmax=108</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td nowrap colspan="4" bgcolor="#FF9966">N unknown</td>
 <td nowrap colspan="4" bgcolor="#FF9966">N known</td>
 </tr>
 <tr align="center" valign="middle"> 
 <td width="20%" nowrap align="center" valign="middle" colspan="13" bgcolor="#33CC66">Required 
 main memory [MB]</td>
 </tr>
</table>

Implementation:

After: Gurmeet Singh Manku, Sridhar Rajagopalan and Bruce G. Lindsay,
Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets.
Proc. of the 1999 ACM SIGMOD Int. Conf. on Management of Data,
Paper available <A HREF="http://www-cad.eecs.berkeley.edu/~manku/papers/unknown.ps.gz"> here</A>.

and

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 <A HREF="http://www-cad.eecs.berkeley.edu/~manku/papers/quantiles.ps.gz"> here</A>.

The broad picture is as follows. Two concepts are used: Shrinking and Sampling.
Shrinking takes a data sequence, sorts it and produces a shrinked data sequence by picking every k-th element and throwing away all the rest.
The shrinked data sequence is an approximation to the original data sequence.

Imagine a large data sequence (residing on disk or being generated in memory on the fly) and a main memory block of <tt>n=b*k</tt> elements (<tt>b</tt> is the number of buffers, <tt>k</tt> is the number of elements per buffer). 
Fill elements from the data sequence into the block until it is full or the data sequence is exhausted.
When the block (or a subset of buffers) is full and the data sequence is not exhausted, apply shrinking to lossily compress a number of buffers into one single buffer.
Repeat these steps until all elements of the data sequence have been consumed.
Now the block is a shrinked approximation of the original data sequence. 
Treating it as if it would be the original data sequence, we can determine quantiles in main memory.

Now, the whole thing boils down to the question of: Can we choose <tt>b</tt> and <tt>k</tt> (the number of buffers and the buffer size) such that <tt>b*k</tt> is minimized, 
yet quantiles determined upon the block are guaranteed to be away from the true quantiles no more than some <tt>epsilon</tt>?
It turns out, we can. It also turns out that the required main memory block size <tt>n=b*k</tt> is usually moderate (see the table above).

The theme can be combined with random sampling to further reduce main memory requirements, at the expense of probabilistic guarantees.
Sampling filters the data sequence and feeds only selected elements to the algorithm outlined above.
Sampling is turned on or off, depending on the parametrization.

This quick overview does not go into important details, such as assigning proper weights to buffers, how to choose subsets of buffers to shrink, etc. 
For more information consult the papers cited above.

Time Performance:

<div align="center">Pentium Pro 200 Mhz, SunJDK 1.2.2, NT, java -classic, 
 filling 10 4 elements at a time, reading 100 percentiles at a time, 
 hasSumOfLogarithms()=false, hasSumOfInversions()=false, getMaxOrderForSumOfPowers()=2 
</div>
<center>
 <table border cellpadding="6" cellspacing="0" align="center" width="623">
 <tr valign="middle"> 
 <td align="center" height="50" colspan="9" bgcolor="#33CC66" nowrap> Performance</td>
 </tr>
 <tr valign="middle"> 
 <td align="center" width="56" height="100" rowspan="2" bgcolor="#FF9966" nowrap> 
 Quantiles</td>
 <td align="center" width="44" height="100" rowspan="2" bgcolor="#FF9966" nowrap> 
 Epsilon</td>
 <td align="center" width="32" height="100" rowspan="2" bgcolor="#FF9966" nowrap> 
 Delta</td>
 <td align="center" width="1" height="150" rowspan="7" nowrap>&nbsp; </td>
 <td align="center" height="50" colspan="2" bgcolor="#33CC66" nowrap> Filling 
 
 [#elements/sec] </td>
 <td align="center" width="1" height="150" rowspan="7" nowrap>&nbsp; </td>
 <td align="center" height="50" colspan="2" bgcolor="#33CC66"> Quantile 
 computation 
 [#quantiles/sec] </td>
 </tr>
 <tr valign="middle" bgcolor="#FF9966" nowrap> 
 <td align="center" width="75" height="50" nowrap valign="middle"> N 
 unknown, 
 Nmax=inf</td>
 <td align="center" width="77" height="50" nowrap valign="middle"> N 
 known, 
 Nmax=107 </td>
 <td align="center" width="106" height="50" nowrap valign="middle"> N 
 unknown, 
 Nmax=inf</td>
 <td align="center" width="103" height="50" nowrap valign="middle"> N 
 known, 
 Nmax=107 </td>
 </tr>
 <tr valign="middle"> 
 <td align="center" height="31" colspan="3" nowrap>&nbsp; </td>
 <td align="center" height="31" colspan="2" nowrap>&nbsp; </td>
 <td align="center" height="31" colspan="2" nowrap>&nbsp; </td>
 </tr>
 <tr valign="middle"> 
 <td align="center" width="56" rowspan="4" bgcolor="#FFCCCC" nowrap> 104</td>
 <td align="center" width="44" bgcolor="#FFCCCC" nowrap> 10 -1</td>
 <td align="center" width="32" bgcolor="#FFCCCC" nowrap rowspan="4"> 10 
 -1 </td>
 <td width="75" bgcolor="#66CCFF" nowrap align="center"> 
 1600000
 </td>
 <td width="77" bgcolor="#66CCFF" nowrap align="center">1300000</td>
 <td align="center" width="106" bgcolor="#66CCFF" nowrap>250000 </td>
 <td align="center" width="103" bgcolor="#66CCFF" nowrap>130000 </td>
 </tr>
 <tr valign="middle"> 
 <td align="center" width="44" bgcolor="#FFCCCC"> 10 -2</td>
 <td width="75" bgcolor="#66CCFF" align="center">360000</td>
 <td width="77" bgcolor="#66CCFF" align="center">1200000</td>
 <td align="center" width="106" bgcolor="#66CCFF">50000 </td>
 <td align="center" width="103" bgcolor="#66CCFF">20000 </td>
 </tr>
 <tr valign="middle"> 
 <td align="center" width="44" bgcolor="#FFCCCC"> 10 -3</td>
 <td width="75" bgcolor="#66CCFF" align="center">150000</td>
 <td width="77" bgcolor="#66CCFF" align="center">200000</td>
 <td align="center" width="106" bgcolor="#66CCFF">3600 </td>
 <td align="center" width="103" bgcolor="#66CCFF">3000 </td>
 </tr>
 <tr valign="middle"> 
 <td align="center" width="44" bgcolor="#FFCCCC"> 10 -4</td>
 <td width="75" bgcolor="#66CCFF" align="center">120000</td>
 <td width="77" bgcolor="#66CCFF" align="center">170000</td>
 <td align="center" width="106" bgcolor="#66CCFF">80 </td>
 <td align="center" width="103" bgcolor="#66CCFF">1000 </td>
 </tr>
 </table>
</center>

<DL>
<DT>Version:</DT>
 <DD>0.9, 03-Jul-99</DD>
<DT>See Also:<DD><A HREF="../../../cern/jet/stat/quantile/package-summary.html"><CODE>cern.jet.stat.quantile</CODE></A>, 
<A HREF="../../../serialized-form.html#hep.aida.bin.QuantileBin1D">Serialized Form</A></DL>
<HR>

<A NAME="field_summary"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
<TD COLSPAN=2>
Field Summary</TD>
</TR>
</TABLE>
&nbsp;<A NAME="fields_inherited_from_class_cern.colt.PersistentObject"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#EEEEFF" CLASS="TableSubHeadingColor">
<TD>Fields inherited from class cern.colt.<A HREF="../../../cern/colt/PersistentObject.html" title="class in cern.colt">PersistentObject</A></TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD><CODE><A HREF="../../../cern/colt/PersistentObject.html#serialVersionUID">serialVersionUID</A></CODE></TD>
</TR>
</TABLE>
&nbsp;

<A NAME="constructor_summary"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
<TD COLSPAN=2>
Constructor Summary</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#QuantileBin1D(boolean, long, double, double, int, cern.jet.random.engine.RandomEngine)">QuantileBin1D</A>(boolean&nbsp;known_N,
 long&nbsp;N,
 double&nbsp;epsilon,
 double&nbsp;delta,
 int&nbsp;quantiles,
 <A HREF="../../../cern/jet/random/engine/RandomEngine.html" title="class in cern.jet.random.engine">RandomEngine</A>&nbsp;randomGenerator)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Equivalent to <tt>new QuantileBin1D(known_N, N, epsilon, delta, quantiles, randomGenerator, false, false, 2)</tt>.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#QuantileBin1D(boolean, long, double, double, int, cern.jet.random.engine.RandomEngine, boolean, boolean, int)">QuantileBin1D</A>(boolean&nbsp;known_N,
 long&nbsp;N,
 double&nbsp;epsilon,
 double&nbsp;delta,
 int&nbsp;quantiles,
 <A HREF="../../../cern/jet/random/engine/RandomEngine.html" title="class in cern.jet.random.engine">RandomEngine</A>&nbsp;randomGenerator,
 boolean&nbsp;hasSumOfLogarithms,
 boolean&nbsp;hasSumOfInversions,
 int&nbsp;maxOrderForSumOfPowers)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Constructs and returns an empty bin that, under the given constraints, minimizes the amount of memory needed.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#QuantileBin1D(double)">QuantileBin1D</A>(double&nbsp;epsilon)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Equivalent to <tt>new QuantileBin1D(false, Long.MAX_VALUE, epsilon, 0.001, 10000, new cern.jet.random.engine.DRand(new java.util.Date())</tt>.</TD>
</TR>
</TABLE>
&nbsp;

<A NAME="method_summary"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
<TD COLSPAN=2>
Method Summary</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;void</CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#addAllOfFromTo(cern.colt.list.DoubleArrayList, int, int)">addAllOfFromTo</A>(<A HREF="../../../cern/colt/list/DoubleArrayList.html" title="class in cern.colt.list">DoubleArrayList</A>&nbsp;list,
 int&nbsp;from,
 int&nbsp;to)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Adds the part of the specified list between indexes <tt>from</tt> (inclusive) and <tt>to</tt> (inclusive) to the receiver.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;void</CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#clear()">clear</A>()</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Removes all elements from the receiver.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;<A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html" title="class or interface in java.lang">Object</A></CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#clone()">clone</A>()</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Returns a deep copy of the receiver.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;<A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/String.html" title="class or interface in java.lang">String</A></CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#compareWith(hep.aida.bin.AbstractBin1D)">compareWith</A>(<A HREF="../../../hep/aida/bin/AbstractBin1D.html" title="class in hep.aida.bin">AbstractBin1D</A>&nbsp;other)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Computes the deviations from the receiver's measures to another bin's measures.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;double</CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#median()">median</A>()</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Returns the median.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;double</CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#quantile(double)">quantile</A>(double&nbsp;phi)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Computes and returns the phi-quantile.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;double</CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#quantileInverse(double)">quantileInverse</A>(double&nbsp;element)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Returns how many percent of the elements contained in the receiver are <tt>&lt;= element</tt>.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;<A HREF="../../../cern/colt/list/DoubleArrayList.html" title="class in cern.colt.list">DoubleArrayList</A></CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#quantiles(cern.colt.list.DoubleArrayList)">quantiles</A>(<A HREF="../../../cern/colt/list/DoubleArrayList.html" title="class in cern.colt.list">DoubleArrayList</A>&nbsp;phis)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Returns the quantiles of the specified percentages.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;int</CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#sizeOfRange(double, double)">sizeOfRange</A>(double&nbsp;minElement,
 double&nbsp;maxElement)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Returns how many elements are contained in the range <tt>[minElement,maxElement]</tt>.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;<A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">MightyStaticBin1D</A>[]</CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#splitApproximately(cern.colt.list.DoubleArrayList, int)">splitApproximately</A>(<A HREF="../../../cern/colt/list/DoubleArrayList.html" title="class in cern.colt.list">DoubleArrayList</A>&nbsp;percentages,
 int&nbsp;k)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Divides (rebins) a copy of the receiver at the given percentage boundaries into bins and returns these bins, such that each bin approximately reflects the data elements of its range.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;<A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">MightyStaticBin1D</A>[]</CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#splitApproximately(hep.aida.IAxis, int)">splitApproximately</A>(<A HREF="../../../hep/aida/IAxis.html" title="interface in hep.aida">IAxis</A>&nbsp;axis,
 int&nbsp;k)</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Divides (rebins) a copy of the receiver at the given interval boundaries into bins and returns these bins, such that each bin approximately reflects the data elements of its range.</TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD ALIGN="right" VALIGN="top" WIDTH="1%">
<CODE>&nbsp;<A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/String.html" title="class or interface in java.lang">String</A></CODE></TD>
<TD><CODE><A HREF="../../../hep/aida/bin/QuantileBin1D.html#toString()">toString</A>()</CODE>

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Returns a String representation of the receiver.</TD>
</TR>
</TABLE>
&nbsp;<A NAME="methods_inherited_from_class_hep.aida.bin.MightyStaticBin1D"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#EEEEFF" CLASS="TableSubHeadingColor">
<TD>Methods inherited from class hep.aida.bin.<A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">MightyStaticBin1D</A></TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD><CODE><A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#geometricMean()">geometricMean</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#getMaxOrderForSumOfPowers()">getMaxOrderForSumOfPowers</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#getMinOrderForSumOfPowers()">getMinOrderForSumOfPowers</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#harmonicMean()">harmonicMean</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#hasSumOfInversions()">hasSumOfInversions</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#hasSumOfLogarithms()">hasSumOfLogarithms</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#hasSumOfPowers(int)">hasSumOfPowers</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#kurtosis()">kurtosis</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#moment(int, double)">moment</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#product()">product</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#skew()">skew</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#sumOfInversions()">sumOfInversions</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#sumOfLogarithms()">sumOfLogarithms</A>, <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#sumOfPowers(int)">sumOfPowers</A></CODE></TD>
</TR>
</TABLE>
&nbsp;<A NAME="methods_inherited_from_class_hep.aida.bin.StaticBin1D"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#EEEEFF" CLASS="TableSubHeadingColor">
<TD>Methods inherited from class hep.aida.bin.<A HREF="../../../hep/aida/bin/StaticBin1D.html" title="class in hep.aida.bin">StaticBin1D</A></TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD><CODE><A HREF="../../../hep/aida/bin/StaticBin1D.html#add(double)">add</A>, <A HREF="../../../hep/aida/bin/StaticBin1D.html#isRebinnable()">isRebinnable</A>, <A HREF="../../../hep/aida/bin/StaticBin1D.html#max()">max</A>, <A HREF="../../../hep/aida/bin/StaticBin1D.html#min()">min</A>, <A HREF="../../../hep/aida/bin/StaticBin1D.html#size()">size</A>, <A HREF="../../../hep/aida/bin/StaticBin1D.html#sum()">sum</A>, <A HREF="../../../hep/aida/bin/StaticBin1D.html#sumOfSquares()">sumOfSquares</A></CODE></TD>
</TR>
</TABLE>
&nbsp;<A NAME="methods_inherited_from_class_hep.aida.bin.AbstractBin1D"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#EEEEFF" CLASS="TableSubHeadingColor">
<TD>Methods inherited from class hep.aida.bin.<A HREF="../../../hep/aida/bin/AbstractBin1D.html" title="class in hep.aida.bin">AbstractBin1D</A></TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD><CODE><A HREF="../../../hep/aida/bin/AbstractBin1D.html#addAllOf(cern.colt.list.DoubleArrayList)">addAllOf</A>, <A HREF="../../../hep/aida/bin/AbstractBin1D.html#buffered(int)">buffered</A>, <A HREF="../../../hep/aida/bin/AbstractBin1D.html#equals(java.lang.Object)">equals</A>, <A HREF="../../../hep/aida/bin/AbstractBin1D.html#mean()">mean</A>, <A HREF="../../../hep/aida/bin/AbstractBin1D.html#rms()">rms</A>, <A HREF="../../../hep/aida/bin/AbstractBin1D.html#standardDeviation()">standardDeviation</A>, <A HREF="../../../hep/aida/bin/AbstractBin1D.html#standardError()">standardError</A>, <A HREF="../../../hep/aida/bin/AbstractBin1D.html#trimToSize()">trimToSize</A>, <A HREF="../../../hep/aida/bin/AbstractBin1D.html#variance()">variance</A></CODE></TD>
</TR>
</TABLE>
&nbsp;<A NAME="methods_inherited_from_class_hep.aida.bin.AbstractBin"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#EEEEFF" CLASS="TableSubHeadingColor">
<TD>Methods inherited from class hep.aida.bin.<A HREF="../../../hep/aida/bin/AbstractBin.html" title="class in hep.aida.bin">AbstractBin</A></TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD><CODE><A HREF="../../../hep/aida/bin/AbstractBin.html#center()">center</A>, <A HREF="../../../hep/aida/bin/AbstractBin.html#center(int)">center</A>, <A HREF="../../../hep/aida/bin/AbstractBin.html#error()">error</A>, <A HREF="../../../hep/aida/bin/AbstractBin.html#error(int)">error</A>, <A HREF="../../../hep/aida/bin/AbstractBin.html#offset()">offset</A>, <A HREF="../../../hep/aida/bin/AbstractBin.html#offset(int)">offset</A>, <A HREF="../../../hep/aida/bin/AbstractBin.html#value()">value</A>, <A HREF="../../../hep/aida/bin/AbstractBin.html#value(int)">value</A></CODE></TD>
</TR>
</TABLE>
&nbsp;<A NAME="methods_inherited_from_class_java.lang.Object"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#EEEEFF" CLASS="TableSubHeadingColor">
<TD>Methods inherited from class java.lang.<A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html" title="class or interface in java.lang">Object</A></TD>
</TR>
<TR BGCOLOR="white" CLASS="TableRowColor">
<TD><CODE><A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#getClass()" title="class or interface in java.lang">getClass</A>, <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#hashCode()" title="class or interface in java.lang">hashCode</A>, <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#notify()" title="class or interface in java.lang">notify</A>, <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#notifyAll()" title="class or interface in java.lang">notifyAll</A>, <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#wait()" title="class or interface in java.lang">wait</A>, <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#wait(long)" title="class or interface in java.lang">wait</A>, <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#wait(long, int)" title="class or interface in java.lang">wait</A></CODE></TD>
</TR>
</TABLE>
&nbsp;

<A NAME="constructor_detail"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
<TD COLSPAN=1>
Constructor Detail</TD>
</TR>
</TABLE>

<A NAME="QuantileBin1D(double)"></A><H3>
QuantileBin1D</H3>
<PRE>
public QuantileBin1D(double&nbsp;epsilon)</PRE>
<DL>
<DD>Equivalent to <tt>new QuantileBin1D(false, Long.MAX_VALUE, epsilon, 0.001, 10000, new cern.jet.random.engine.DRand(new java.util.Date())</tt>.

</DL>
<HR>

<A NAME="QuantileBin1D(boolean, long, double, double, int, cern.jet.random.engine.RandomEngine)"></A><H3>
QuantileBin1D</H3>
<PRE>
public QuantileBin1D(boolean&nbsp;known_N,
 long&nbsp;N,
 double&nbsp;epsilon,
 double&nbsp;delta,
 int&nbsp;quantiles,
 <A HREF="../../../cern/jet/random/engine/RandomEngine.html" title="class in cern.jet.random.engine">RandomEngine</A>&nbsp;randomGenerator)</PRE>
<DL>
<DD>Equivalent to <tt>new QuantileBin1D(known_N, N, epsilon, delta, quantiles, randomGenerator, false, false, 2)</tt>.

</DL>
<HR>

<A NAME="QuantileBin1D(boolean, long, double, double, int, cern.jet.random.engine.RandomEngine, boolean, boolean, int)"></A><H3>
QuantileBin1D</H3>
<PRE>
public QuantileBin1D(boolean&nbsp;known_N,
 long&nbsp;N,
 double&nbsp;epsilon,
 double&nbsp;delta,
 int&nbsp;quantiles,
 <A HREF="../../../cern/jet/random/engine/RandomEngine.html" title="class in cern.jet.random.engine">RandomEngine</A>&nbsp;randomGenerator,
 boolean&nbsp;hasSumOfLogarithms,
 boolean&nbsp;hasSumOfInversions,
 int&nbsp;maxOrderForSumOfPowers)</PRE>
<DL>
<DD>Constructs and returns an empty bin that, under the given constraints, minimizes the amount of memory needed.
 
 Some applications exactly know in advance over how many elements quantiles are to be computed.
 Provided with such information the main memory requirements of this class are small.
 Other applications don't know in advance over how many elements quantiles are to be computed.
 However, some of them can give an upper limit, which will reduce main memory requirements.
 For example, if elements are selected from a database and filled into histograms, it is usually not known in advance how many elements are being filled, but one may know that at most <tt>S</tt> elements, the number of elements in the database, are filled.
 A third type of application knowns nothing at all about the number of elements to be filled;
 from zero to infinitely many elements may actually be filled.
 This method efficiently supports all three types of applications.

<DT>Parameters:<DD><CODE>known_N</CODE> - specifies whether the number of elements over which quantiles are to be computed is known or not.
 <DD><CODE>N</CODE> - if <tt>known_N==true</tt>, the number of elements over which quantiles are to be computed.
			if <tt>known_N==false</tt>, the upper limit on the number of elements over which quantiles are to be computed.
 In other words, the maximum number of elements ever to be added.
 			If such an upper limit is a-priori unknown, then set <tt>N = Long.MAX_VALUE</tt>.
 <DD><CODE>epsilon</CODE> - the approximation error which is guaranteed not to be exceeded (e.g. <tt>0.001</tt>) (<tt>0 &lt;= epsilon &lt;= 1</tt>). 
 To get exact rather than approximate quantiles, set <tt>epsilon=0.0</tt>;
 <DD><CODE>delta</CODE> - the allowed probability that the actual approximation error exceeds <tt>epsilon</tt> (e.g. 0.0001) (0 &lt;= delta &lt;= 1). 
 To avoid probabilistic answers, set <tt>delta=0.0</tt>.
 For example, <tt>delta = 0.0001</tt> is equivalent to a confidence of <tt>99.99%</tt>.
 <DD><CODE>quantiles</CODE> - the number of quantiles to be computed (e.g. <tt>100</tt>) (<tt>quantiles &gt;= 1</tt>). 
 If unknown in advance, set this number large, e.g. <tt>quantiles &gt;= 10000</tt>.
 <DD><CODE>hasSumOfLogarithms</CODE> - Tells whether <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#sumOfLogarithms()"><CODE>MightyStaticBin1D.sumOfLogarithms()</CODE></A> can return meaningful results.
 Set this parameter to <tt>false</tt> if measures of sum of logarithms, geometric mean and product are not required.
 <DD><CODE>hasSumOfInversions</CODE> - Tells whether <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#sumOfInversions()"><CODE>MightyStaticBin1D.sumOfInversions()</CODE></A> can return meaningful results.
 Set this parameter to <tt>false</tt> if measures of sum of inversions, harmonic mean and sumOfPowers(-1) are not required.
 <DD><CODE>maxOrderForSumOfPowers</CODE> - The maximum order <tt>k</tt> for which <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#sumOfPowers(int)"><CODE>MightyStaticBin1D.sumOfPowers(int)</CODE></A> can return meaningful results.
 Set this parameter to at least 3 if the skew is required, to at least 4 if the kurtosis is required.
 In general, if moments are required set this parameter at least as large as the largest required moment.
 This method always substitutes <tt>Math.max(2,maxOrderForSumOfPowers)</tt> for the parameter passed in.
 Thus, <tt>sumOfPowers(0..2)</tt> always returns meaningful results.</DL>

<A NAME="method_detail"></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
<TD COLSPAN=1>
Method Detail</TD>
</TR>
</TABLE>

<A NAME="addAllOfFromTo(cern.colt.list.DoubleArrayList, int, int)"></A><H3>
addAllOfFromTo</H3>
<PRE>
public void addAllOfFromTo(<A HREF="../../../cern/colt/list/DoubleArrayList.html" title="class in cern.colt.list">DoubleArrayList</A>&nbsp;list,
 int&nbsp;from,
 int&nbsp;to)</PRE>
<DL>
<DD>Adds the part of the specified list between indexes <tt>from</tt> (inclusive) and <tt>to</tt> (inclusive) to the receiver.

<DD><DL>
<DT>Overrides:<DD><CODE><A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#addAllOfFromTo(cern.colt.list.DoubleArrayList, int, int)">addAllOfFromTo</A></CODE> in class <CODE><A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">MightyStaticBin1D</A></CODE></DL>
</DD>
<DD><DL>
<DT>Parameters:<DD><CODE>list</CODE> - the list of which elements shall be added.<DD><CODE>from</CODE> - the index of the first element to be added (inclusive).<DD><CODE>to</CODE> - the index of the last element to be added (inclusive).
<DT>Throws:
<DD><CODE><A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/IndexOutOfBoundsException.html" title="class or interface in java.lang">IndexOutOfBoundsException</A></CODE> - if <tt>list.size()&gt;0 && (from&lt;0 || from&gt;to || to&gt;=list.size())</tt>.</DL>
</DD>
</DL>
<HR>

<A NAME="clear()"></A><H3>
clear</H3>
<PRE>
public void clear()</PRE>
<DL>
<DD>Removes all elements from the receiver.
 The receiver will be empty after this call returns.

<DD><DL>
<DT>Overrides:<DD><CODE><A HREF="../../../hep/aida/bin/StaticBin1D.html#clear()">clear</A></CODE> in class <CODE><A HREF="../../../hep/aida/bin/StaticBin1D.html" title="class in hep.aida.bin">StaticBin1D</A></CODE></DL>
</DD>
<DD><DL>
</DL>
</DD>
</DL>
<HR>

<A NAME="clone()"></A><H3>
clone</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/Object.html" title="class or interface in java.lang">Object</A> clone()</PRE>
<DL>
<DD>Returns a deep copy of the receiver.

<DD><DL>
<DT>Overrides:<DD><CODE><A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#clone()">clone</A></CODE> in class <CODE><A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">MightyStaticBin1D</A></CODE></DL>
</DD>
<DD><DL>

<DT>Returns:<DD>a deep copy of the receiver.</DL>
</DD>
</DL>
<HR>

<A NAME="compareWith(hep.aida.bin.AbstractBin1D)"></A><H3>
compareWith</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/String.html" title="class or interface in java.lang">String</A> compareWith(<A HREF="../../../hep/aida/bin/AbstractBin1D.html" title="class in hep.aida.bin">AbstractBin1D</A>&nbsp;other)</PRE>
<DL>
<DD>Computes the deviations from the receiver's measures to another bin's measures.

<DD><DL>
<DT>Overrides:<DD><CODE><A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#compareWith(hep.aida.bin.AbstractBin1D)">compareWith</A></CODE> in class <CODE><A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">MightyStaticBin1D</A></CODE></DL>
</DD>
<DD><DL>
<DT>Parameters:<DD><CODE>other</CODE> - the other bin to compare with
<DT>Returns:<DD>a summary of the deviations.</DL>
</DD>
</DL>
<HR>

<A NAME="median()"></A><H3>
median</H3>
<PRE>
public double median()</PRE>
<DL>
<DD>Returns the median.

<DD><DL>
</DL>
</DD>
</DL>
<HR>

<A NAME="quantile(double)"></A><H3>
quantile</H3>
<PRE>
public double quantile(double&nbsp;phi)</PRE>
<DL>
<DD>Computes and returns the phi-quantile.

<DD><DL>
<DT>Parameters:<DD><CODE>phi</CODE> - the percentage for which the quantile is to be computed.
 phi must be in the interval <tt>(0.0,1.0]</tt>.
<DT>Returns:<DD>the phi quantile element.</DL>
</DD>
</DL>
<HR>

<A NAME="quantileInverse(double)"></A><H3>
quantileInverse</H3>
<PRE>
public double quantileInverse(double&nbsp;element)</PRE>
<DL>
<DD>Returns how many percent of the elements contained in the receiver are <tt>&lt;= element</tt>.
 Does linear interpolation if the element is not contained but lies in between two contained elements.

<DD><DL>

<DT>Returns:<DD>the percentage <tt>phi</tt> of elements <tt>&lt;= element</tt> (<tt>0.0 &lt;= phi &lt;=1.0)</tt>.</DL>
</DD>
</DL>
<HR>

<A NAME="quantiles(cern.colt.list.DoubleArrayList)"></A><H3>
quantiles</H3>
<PRE>
public <A HREF="../../../cern/colt/list/DoubleArrayList.html" title="class in cern.colt.list">DoubleArrayList</A> quantiles(<A HREF="../../../cern/colt/list/DoubleArrayList.html" title="class in cern.colt.list">DoubleArrayList</A>&nbsp;phis)</PRE>
<DL>
<DD>Returns the quantiles of the specified percentages.
 For implementation reasons considerably more efficient than calling <A HREF="../../../hep/aida/bin/QuantileBin1D.html#quantile(double)"><CODE>quantile(double)</CODE></A> various times.

<DD><DL>

<DT>Returns:<DD>the quantiles.</DL>
</DD>
</DL>
<HR>

<A NAME="sizeOfRange(double, double)"></A><H3>
sizeOfRange</H3>
<PRE>
public int sizeOfRange(double&nbsp;minElement,
 double&nbsp;maxElement)</PRE>
<DL>
<DD>Returns how many elements are contained in the range <tt>[minElement,maxElement]</tt>.
 Does linear interpolation if one or both of the parameter elements are not contained.
 Returns exact or approximate results, depending on the parametrization of this class or subclasses.

<DD><DL>
<DT>Parameters:<DD><CODE>minElement</CODE> - the minimum element to search for.<DD><CODE>maxElement</CODE> - the maximum element to search for.
<DT>Returns:<DD>the number of elements in the range.</DL>
</DD>
</DL>
<HR>

<A NAME="splitApproximately(cern.colt.list.DoubleArrayList, int)"></A><H3>
splitApproximately</H3>
<PRE>
public <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">MightyStaticBin1D</A>[] splitApproximately(<A HREF="../../../cern/colt/list/DoubleArrayList.html" title="class in cern.colt.list">DoubleArrayList</A>&nbsp;percentages,
 int&nbsp;k)</PRE>
<DL>
<DD>Divides (rebins) a copy of the receiver at the given percentage boundaries into bins and returns these bins, such that each bin approximately reflects the data elements of its range.

The receiver is not physically rebinned (divided); it stays unaffected by this operation.
The returned bins are such that if one would have filled elements into multiple bins
instead of one single all encompassing bin only, those multiple bins would have approximately the same statistics measures as the one's returned by this method.

The <tt>split(...)</tt> methods are particularly well suited for real-time interactive rebinning (the famous "scrolling slider" effect).

Passing equi-distant percentages like <tt>(0.0, 0.2, 0.4, 0.6, 0.8, 1.0)</tt> into this method will yield bins of an equi-depth histogram, i.e. a histogram with bin boundaries adjusted such that each bin contains the same number of elements, in this case 20% each.
Equi-depth histograms can be useful if, for example, not enough properties of the data to be captured are known a-priori to be able to define reasonable bin boundaries (partitions).
For example, when guesses about minimas and maximas are strongly unreliable.
Or when chances are that by focussing too much on one particular area other important areas and characters of a data set may be missed.

Implementation:

The receiver is divided into <tt>s = percentages.size()-1</tt> intervals (bins).
For each interval <tt>I</tt>, its minimum and maximum elements are determined based upon quantile computation.
Further, each interval <tt>I</tt> is split into <tt>k</tt> equi-percent-distant subintervals (sub-bins).
In other words, an interval is split into subintervals such that each subinterval contains the same number of elements.

For each subinterval <tt>S</tt>, its minimum and maximum are determined, again, based upon quantile computation.
They yield an approximate arithmetic mean <tt>am = (min+max)/2</tt> of the subinterval.
A subinterval is treated as if it would contain only elements equal to the mean <tt>am</tt>.
Thus, if the subinterval contains, say, <tt>n</tt> elements, it is assumed to consist of <tt>n</tt> mean elements <tt>(am,am,...,am)</tt>.
A subinterval's sum of elements, sum of squared elements, sum of inversions, etc. are then approximated using such a sequence of mean elements.

Finally, the statistics measures of an interval <tt>I</tt> are computed by summing up (integrating) the measures of its subintervals.

Accuracy:

Depending on the accuracy of quantile computation and the number of subintervals per interval (the resolution).
Objects of this class compute exact or approximate quantiles, depending on the parameters used upon instance construction.
Objects of subclasses may always compute exact quantiles, as is the case for <A HREF="../../../hep/aida/bin/DynamicBin1D.html" title="class in hep.aida.bin"><CODE>DynamicBin1D</CODE></A>.
Most importantly for this class <tt>QuantileBin1D</tt>, a reasonably small epsilon (e.g. 0.01, perhaps 0.001) should be used upon instance construction.
The confidence parameter <tt>delta</tt> is less important, you may find <tt>delta=0.00001</tt> appropriate.
 
The larger the resolution, the smaller the approximation error, up to some limit.
Integrating over only a few subintervals per interval will yield very crude approximations.
If the resolution is set to a reasonably large number, say 10..100, more small subintervals are integrated, resulting in more accurate results.
 
Note that for good accuracy, the number of quantiles computable with the given approximation guarantees should upon instance construction be specified, so as to satisfy

<tt>quantiles > resolution * (percentages.size()-1)</tt>


Example:

<tt>resolution=2, percentList = (0.0, 0.1, 0.2, 0.5, 0.9, 1.0)</tt> means the receiver is to be split into 5 bins:
 
<ul>
<li>bin 0 ranges from <tt>[0%..10%)</tt> and holds the smallest 10% of the sorted elements.
<li>bin 1 ranges from <tt>[10%..20%)</tt> and holds the next smallest 10% of the sorted elements.
<li>bin 2 ranges from <tt>[20%..50%)</tt> and holds the next smallest 30% of the sorted elements.
<li>bin 3 ranges from <tt>[50%..90%)</tt> and holds the next smallest 40% of the sorted elements.
<li>bin 4 ranges from <tt>[90%..100%)</tt> and holds the largest 10% of the sorted elements.
</ul>

The statistics measures for each bin are to be computed at a resolution of 2 subbins per bin.
Thus, the statistics measures of a bin are the integrated measures over 2 subbins, each containing the same amount of elements:
<ul>
<li>bin 0 has a subbin ranging from <tt>[ 0%.. 5%)</tt> and a subbin ranging from <tt>[ 5%..10%)</tt>.
<li>bin 1 has a subbin ranging from <tt>[10%..15%)</tt> and a subbin ranging from <tt>[15%..20%)</tt>.
<li>bin 2 has a subbin ranging from <tt>[20%..35%)</tt> and a subbin ranging from <tt>[35%..50%)</tt>.
<li>bin 3 has a subbin ranging from <tt>[50%..70%)</tt> and a subbin ranging from <tt>[70%..90%)</tt>.
<li>bin 4 has a subbin ranging from <tt>[90%..95%)</tt> and a subbin ranging from <tt>[95%..100%)</tt>.
</ul>

Lets concentrate on the subbins of bin 0.
<ul>
<li>Assume the subbin <tt>A=[0%..5%)</tt> has a minimum of <tt>300</tt> and a maximum of <tt>350</tt> (0% of all elements are less than 300, 5% of all elements are less than 350).
<li>Assume the subbin <tt>B=[5%..10%)</tt> has a minimum of <tt>350</tt> and a maximum of <tt>550</tt> (5% of all elements are less than 350, 10% of all elements are less than 550).
</ul>

Assume the entire data set consists of <tt>N=100</tt> elements.
<ul>
<li>Then subbin A has an approximate mean of <tt>300+350 / 2 = 325</tt>, 
a size of <tt>N*(5%-0%) = 100*5% = 5</tt> elements, an approximate sum of <tt>325 * 100*5% = 1625</tt>, an approximate sum of squares of <tt>3252 * 100*5% = 528125</tt>, an approximate sum of inversions of <tt>(1.0/325) * 100*5% = 0.015</tt>, etc.
<li>Analogously, subbin B has an approximate mean of <tt>350+550 / 2 = 450</tt>,
a size of <tt>N*(10%-5%) = 100*5% = 5</tt> elements, an approximate sum of <tt>450 * 100*5% = 2250</tt>, an approximate sum of squares of <tt>4502 * 100*5% = 1012500</tt>, an approximate sum of inversions of <tt>(1.0/450) * 100*5% = 0.01</tt>, etc.
</ul>

Finally, the statistics measures of bin 0 are computed by summing up (integrating) the measures of its subintervals:
Bin 0 has a size of <tt>N*(10%-0%)=10</tt> elements (we knew that already), sum of <tt>1625+2250=3875</tt>, sum of squares of <tt>528125+1012500=1540625</tt>, sum of inversions of <tt>0.015+0.01=0.025</tt>, etc.
From these follow other measures such as <tt>mean=3875/10=387.5, rms = sqrt(1540625 / 10)=392.5</tt>, etc.
The other bins are computes analogously.

<DD><DL>
<DT>Parameters:<DD><CODE>percentages</CODE> - the percentage boundaries at which the receiver shall be split.</DL>
</DD>
</DL>
<HR>

<A NAME="splitApproximately(hep.aida.IAxis, int)"></A><H3>
splitApproximately</H3>
<PRE>
public <A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">MightyStaticBin1D</A>[] splitApproximately(<A HREF="../../../hep/aida/IAxis.html" title="interface in hep.aida">IAxis</A>&nbsp;axis,
 int&nbsp;k)</PRE>
<DL>
<DD>Divides (rebins) a copy of the receiver at the given interval boundaries into bins and returns these bins, such that each bin approximately reflects the data elements of its range.

For each interval boundary of the axis (including -infinity and +infinity), computes the percentage (quantile inverse) of elements less than the boundary.
Then lets <A HREF="../../../hep/aida/bin/QuantileBin1D.html#splitApproximately(cern.colt.list.DoubleArrayList, int)"><CODE>splitApproximately(DoubleArrayList,int)</CODE></A> do the real work.

<DD><DL>
<DT>Parameters:<DD><CODE>axis</CODE> - an axis defining interval boundaries.</DL>
</DD>
</DL>
<HR>

<A NAME="toString()"></A><H3>
toString</H3>
<PRE>
public <A HREF="http://java.sun.com/j2se/1.4/docs/api/java/lang/String.html" title="class or interface in java.lang">String</A> toString()</PRE>
<DL>
<DD>Returns a String representation of the receiver.

<DD><DL>
<DT>Overrides:<DD><CODE><A HREF="../../../hep/aida/bin/MightyStaticBin1D.html#toString()">toString</A></CODE> in class <CODE><A HREF="../../../hep/aida/bin/MightyStaticBin1D.html" title="class in hep.aida.bin">MightyStaticBin1D</A></CODE></DL>
</DD>
<DD><DL>
</DL>
</DD>
</DL>

<HR>

<A NAME="navbar_bottom"></A>
<A HREF="#skip-navbar_bottom" title="Skip navigation links"></A>
<TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY="">
<TR>
<TD COLSPAN=3 BGCOLOR="#EEEEFF" CLASS="NavBarCell1">
<A NAME="navbar_bottom_firstrow"></A>
<TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY="">
 <TR ALIGN="center" VALIGN="top">
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../overview-summary.html">Overview</A>&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-summary.html">Package</A>&nbsp;</TD>
 <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> &nbsp;Class&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="class-use/QuantileBin1D.html">Use</A>&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="package-tree.html">Tree</A>&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../deprecated-list.html">Deprecated</A>&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../index-files/index-1.html">Index</A>&nbsp;</TD>
 <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1"> <A HREF="../../../help-doc.html">Help</A>&nbsp;</TD>
 </TR>
</TABLE>
</TD>
<TD ALIGN="right" VALIGN="top" ROWSPAN=3>
Colt 1.2.0
</TD>
</TR>

</TD>
</TR>
<TR>
<TD VALIGN="top" CLASS="NavBarCell3">
 SUMMARY:&nbsp;NESTED&nbsp;|&nbsp;<A HREF="#fields_inherited_from_class_cern.colt.PersistentObject">FIELD</A>&nbsp;|&nbsp;<A HREF="#constructor_summary">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_summary">METHOD</A></TD>
<TD VALIGN="top" CLASS="NavBarCell3">
DETAIL:&nbsp;FIELD&nbsp;|&nbsp;<A HREF="#constructor_detail">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_detail">METHOD</A></TD>
</TR>
</TABLE>
<A NAME="skip-navbar_bottom"></A>

<HR>
Jump to the <a target=_top href=http://dsd.lbl.gov/~hoschek/colt >Colt Homepage</a>
</BODY>
</HTML>

Rabbit simulation

initial commit