<h2>Median</h2>
<p>Two recent percentile approximation algorithms and their python implementations can be found here:</p>
<p><strong>t-Digests</strong></p>
<ul>
<li><a href="https://arxiv.org/abs/1902.04023" rel="nofollow noreferrer">https://arxiv.org/abs/1902.04023</a></li>
<li><a href="https://github.com/CamDavidsonPilon/tdigest" rel="nofollow noreferrer">https://github.com/CamDavidsonPilon/tdigest</a></li>
</ul>
<p><strong>DDSketch</strong></p>
<ul>
<li><a href="https://arxiv.org/abs/1908.10693" rel="nofollow noreferrer">https://arxiv.org/abs/1908.10693</a></li>
<li><a href="https://github.com/DataDog/sketches-py" rel="nofollow noreferrer">https://github.com/DataDog/sketches-py</a></li>
</ul>
<p>Both algorithms bucket data. As T-Digest uses smaller bins near the tails the
accuracy is better at the extremes (and weaker close to the median). DDSketch additionally provides relative error guarantees.</p>
"On-line" (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?
<p>Is there an algorithm to estimate the median, mode, skewness, and/or kurtosis of set of values, but that does NOT require storing all the values in memory at once?</p>

<p>I'd like to calculate the basic statistics:</p>

<ul>
<li>mean:  arithmetic average</li>
<li>variance:  average of squared deviations from the mean</li>
<li>standard deviation:  square root of the variance</li>
<li>median:  value that separates larger half of the numbers from the smaller half</li>
<li>mode:  most frequent value found in the set</li>
<li>skewness:  tl; dr</li>
<li>kurtosis:  tl; dr</li>
</ul>

<p>The basic formulas for calculating any of these is grade-school arithmetic, and I do know them.  There are many stats libraries that implement them, as well.</p>

<p>My problem is the large number (billions) of values in the sets I'm handling:  Working in Python, I can't just make a list or hash with billions of elements.  Even if I wrote this in C, billion-element arrays aren't too practical.</p>

<p>The data is not sorted.  It's produced randomly, on-the-fly, by other processes.  The size of each set is highly variable, and the sizes will not be known in advance.</p>

<p>I've already figured out how to handle the mean and variance pretty well, iterating through each value in the set in any order.  (Actually, in my case, I take them in the order in which they're generated.)  Here's the algorithm I'm using, courtesy <a href="http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm" rel="noreferrer">http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#On-line_algorithm</a>:</p>

<ul>
<li>Initialize three variables:  count, sum, and sum_of_squares</li>
<li>For each value:

<ul>
<li>Increment count.</li>
<li>Add the value to sum.</li>
<li>Add the square of the value to sum_of_squares.</li>
</ul></li>
<li>Divide sum by count, storing as the variable mean.</li>
<li>Divide sum_of_squares by count, storing as the variable mean_of_squares.</li>
<li>Square mean, storing as square_of_mean.</li>
<li>Subtract square_of_mean from mean_of_squares, storing as variance.</li>
<li>Output mean and variance.</li>
</ul>

<p>This "on-line" algorithm has weaknesses (e.g., accuracy problems as sum_of_squares quickly grows larger than integer range or float precision), but it basically gives me what I need, without having to store every value in each set.</p>

<p>But I don't know whether similar techniques exist for estimating the additional statistics (median, mode, skewness, kurtosis).  I could live with a biased estimator, or even a method that compromises accuracy to a certain degree, as long as the memory required to process N values is substantially less than O(N).</p>

<p>Pointing me to an existing stats library will help, too, if the library has functions to calculate one or more of these operations "on-line".</p>