24

I must clarify immediately that I am a practicing software developer, not a statistician, and that my college stats class was a very long time ago…

That said, I would like to know if there is a method for accumulating a set of descriptive statistics that could then be used to produce a boxplot, that does not entail storing a bunch of individual samples?

What I am trying to do is produce a graphical summary of queue service times within a complex multi-queue process. I have in the past used a package called tnftools that allowed large samples to be accumulated and then post-processed into a nice graph of response times and outliers… But tnftools are not available for my current platform.

Ideally I would like to be able to accumulate a set of descriptive statistics "on the fly" as the process runs, and then extract the data for analysis on demand. But I cannot simply have the process accumulate samples as the memory / IO involved in doing so would have an unacceptable impact on the performance of the system.

Kaelin Colclasure
  • 467
  • 3
  • 7
  • Kaelin:> do you mean whether there exists 'on the fly' method for computing summary stats such as median and quartiles ? If this is what you want i could give you links to papers detailing them. You could also give more details about the platforms you are working on as efficient GNU implementation of these methods likely exists in R. – user603 Oct 06 '10 at 21:24
  • @kwak: Yes, that sounds like what I am looking for. I would greatly appreciate those links. :-) I am working on Mac OS X… I can use R for post-processing data, but can't link GPL code into my company's product for the usual reasons. – Kaelin Colclasure Oct 06 '10 at 23:20

2 Answers2

31

For 'on the fly' boxplot, you will need 'on the fly' min/max (trivial) as well as 'on the fly' quartiles (0.25,0.5=median and 0.75).

A lot of work has been going on recently in the problem of online (or 'on the fly') algorithm for median computation.

A recent developements is binmedian. As a side-kick, it also enjoy better worst case complexity than quickselect (which is neither online nor single pass).

You can find the associated paper as well as C and FORTRAN code online here. You may have to check the licencing details with the authors.

You will also need a single pass algorithm for the quartiles, for which you can use the approach above and the following recursive characterization of the quartiles in terms of medians:

$Q_{0.75}(x) \approx Q_{0.5}(x_i:x_i > Q_{0.5}(x))$

and

$Q_{0.25}(x) \approx Q_{0.5}(x_i:x_i < Q_{0.5}(x))$

i.e. the 25 (75) percent quartile is very close to the median of those observations that are smaller (larger) than the median.

Addendum:

There exist a host of older multi-pass methods for computing quantiles. A popular approach is to maintain/update a deterministically sized reservoir of observations randomly selected from the stream and recursively compute quantiles (see this review) on this reservoir. This (and related) approach are superseded by the one proposed above.

user603
  • 21,225
  • 3
  • 71
  • 135
  • 1
    +1 Right; I was still in dark ages of making approximation from histogram. –  Oct 07 '10 at 08:50
  • Do I understand correctly that such recursive definition of quartiles from medians requires two passes if implemented naively? Are you aware of single pass algorithms? – Quartz Oct 16 '13 at 13:25
  • @Quartz: no, a single pass will do: you have two, single pass, running median computations. – user603 Dec 02 '14 at 20:26
  • 1
    The link is dead, but the paper is available on arxiv: https://arxiv.org/abs/0806.3301 – Tim May 25 '20 at 15:40
3

Instead of just finding the median, there is an algorithm that directly maintains an estimated histogram: "the P-Square Algorithm for Dynamic Calculation of Quantiles and Histograms Without Storing Observations". This will probably be much more efficient that repeated binning for every quantile you want.

Neil G
  • 13,633
  • 3
  • 41
  • 84