I just meant that with the nearly correct estimates from the first pass you could do a more accurate job in the second pass, possibly by partitions, possibly by just applying the incremental algorithm a second time. Because it would have good density estimates from the first pass, it would presumably have better estimates of the sample quantiles the second time around.
On Fri, Sep 17, 2010 at 12:19 PM, Luc Maisonobe <luc.maison...@free.fr>wrote: > > *- use the on-line algorithm mentioned above with two passes, one to > > estimate the quantiles of interest, a second to refine the estimate using > > the actual data. This allows the multiple probe method to be linear in > time > > and should give you exact sample quantiles. It doesn't help the repeated > > probe problem.* > > I'm not sure I understand well. However, the on-line method by itself > would be an interesting addition. It would allow quantiles computation > with the Storeless versions of our classes. >
