Boost C++ Libraries: Ticket #6992: accumulator's median feature skips 1st two data points.

attachment set

polyactis@… — Sat, 16 Jun 2012 01:11:12 GMT

attachment → CalculateMedianMeanOfInputColumn.cc

source code

attachment set

polyactis@… — Sat, 16 Jun 2012 01:11:33 GMT

attachment → CalculateMedianMeanOfInputColumn.h

header file

owner changed

Eric Niebler — Thu, 15 Nov 2012 18:45:12 GMT

owner changed from Eric Niebler to Matthias Troyer

Matthias, can you have a look at this one when you get a chance?

Matthias Troyer — Thu, 15 Nov 2012 20:43:41 GMT

Eric, having dinner with you in Redmond is dangerous especially if I agree to take a look at the open accumulator tickets. Here is my conclusion after looking at the issue:

First, median estimated are notoriously hard and you never get an exact median unless you store at least half of the samples. Hence, unlike the mean which can easily and unambiguously be estimated (as long as the variance is finite), median estimation is harder and different algorithms to estimate the median will give different results.

Our default estimator is a P² quantile estimator, which only stores and updates five numbers and hence has a minimal memory footprint. However, it requires at least five samples before it gives sensible output and I am thus not surprised that using less than five samples does not work.

Shall we throw an exception if the count is less than 5, or just document it more clearly?

owner, status changed

Eric Niebler — Thu, 15 Nov 2012 23:57:15 GMT

owner changed from Matthias Troyer to Eric Niebler
status new → assigned

There are many open accumulator tickets. I only gave you the two that required knowledge of the algorithms that you wrote. :-) Thanks for having a look.

If the precondition of the p² quantile accumulator is that it must have at least 5 samples, then the right thing to do is assert the condition in the accessor. And document it. I'll add this to my to-do list, unless you beat me to it.

Thanks again.

Wed, 14 Dec 2016 11:44:04 GMT

Leaving aside the fact that the point of the P² algorithm is to deal with much larger sample sizes, there is no reason the implementation cannot return the exact median for n <= 5.

It is the P² algorithm's approximation that kicks in when the 6^th observation arrives. Your implementation could simply return the exact median until then.