P² quantile estimator – estimating the median without storing values

Related to this, one of my favourite articles [1] suggests that it’s sufficient to only use one or two pieces of memory to get good estimates. Here’s a pretty amazing result from the paper. To estimate the median (loosely) on a stream, first set the median estimate m to 0 prior to seeing any data. Then as you observe the stream, increase the median estimate m by 1 if the current element s is bigger than m. Do nothing if the current element is the same as m. Decrease the estimate by 1 if the element is less than m. Then (given the right conditions) this process converges to the median. You can even extend this to quantiles by flipping a biased coin and then updating based on the result of the flip as well as the element comparison.<p>The unfortunately now deceased neustar research blog had an interactive widget as well an outstanding write up[2]<p>[1]<a href="https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1407.1121" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;abs&#x2F;1407.1121</a><p>[2] <a href="http:&#x2F;&#x2F;content.research.neustar.biz&#x2F;blog&#x2F;frugal.html" rel="nofollow">http:&#x2F;&#x2F;content.research.neustar.biz&#x2F;blog&#x2F;frugal.html</a>

Great article! One of my favorite data-structures lately is the <a href="https:&#x2F;&#x2F;github.com&#x2F;tdunning&#x2F;t-digest" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;tdunning&#x2F;t-digest</a>. Would be great to see how it compares and what additional accuracy we get but storing some of the data.

One of my favorite problems is solving median based on a stream of data that you can replay, but only using, something like 3 variables of the same type of the data (which I think needs to be integer) from the book Numerical Recipes in FORTRAN.<p>It’s to optimize finding the median from a tape drive in the 70s, but the technique is pretty cute.<p>You make a guess at the median, then basically sum how many are over, and under that value, then guess again until you have an even split.<p>It’s also a problem I like to use to nerd snipe people, because why not.<p>Check my work, because it’s been a long time since I worked with FORTRAN and I could have just remembered incorrectly :)<p><a href="https:&#x2F;&#x2F;github.com&#x2F;jonlighthall&#x2F;nrf77&#x2F;blob&#x2F;master&#x2F;mdian2.f" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;jonlighthall&#x2F;nrf77&#x2F;blob&#x2F;master&#x2F;mdian2.f</a>

I don&#x27;t know much about quantile estimation, so possibly dumb question: why, in the experiments plotted here, does every estimator on every tested distribution underestimate the true median? I expected some errors, but not all systematically in the same direction.

Hi all, in case interesting&#x2F;useful: some research I&#x27;ve been involved in takes a different approach to online quantile estimation (our work is based on Hermite series estimators) and compares favorably to online quantile estimation approaches based on stochastic approximation for example. We&#x27;ve recently released the code:<p><a href="https:&#x2F;&#x2F;github.com&#x2F;MikeJaredS&#x2F;hermiter" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;MikeJaredS&#x2F;hermiter</a><p>I&#x27;ve done some comparisons versus the P^2 algorithm (using the OnlineStats implementation in Julia) and the Hermite series based algorithm appears to have comparable accuracy in the tests conducted. The Hermite based approach has the advantage that it estimates the full quantile function though, so arbitrary quantiles can be obtained at any point in time.

<a href="http:&#x2F;&#x2F;infolab.stanford.edu&#x2F;~datar&#x2F;courses&#x2F;cs361a&#x2F;papers&#x2F;quantiles.pdf" rel="nofollow">http:&#x2F;&#x2F;infolab.stanford.edu&#x2F;~datar&#x2F;courses&#x2F;cs361a&#x2F;papers&#x2F;qua...</a><p>I&#x27;ve found Greenwald-Khanna to be a lot more accurate, and also quite suitable for turning into a visual PDF representation

Have you done a comparison with <a href="https:&#x2F;&#x2F;datasketches.apache.org&#x2F;&#x27;s" rel="nofollow">https:&#x2F;&#x2F;datasketches.apache.org&#x2F;&#x27;s</a> KLL algorithm?

Interesting problem. Access to the last n values isn&#x27;t usually a problem in my own statistical applications, since they are fully RAM-resident to begin with, but it&#x27;s annoying to have to sort N recent values to find the median in an N-wide window. Anyone aware of good shortcuts for that?

I always appreciate alternatives to using an arithmetic mean.