Fetching the paper…

Reading the bibliography…

2008

Fast computation of the median by successive binning

Tibshirani, Ryan J.

Original
PDF
Post on X

Understand

This paper describes a new median algorithm and a median approximation algorithm.

The former has O(n) average running time and the latter has O(n) worst-case running time.
These algorithms are highly competitive with the standard algorithm when computing the median of a single data set, but are significantly faster in updating the median when more data is added.

Fast computation of the median by successive binning · Around

Built on

[] Hoare, C. A. R. (1961), ‘Algorithm 64: Quicksort’, Communications of the ACM
1961
Earlier work this paper cites.
[] Floyd, R. W. & Rivest, R. L. (1975 a
1975
Earlier work this paper cites.

Similar

[] Floyd, R. W. & Rivest, R. L. (1975 b
1975
Cited alongside, same era.
[] Press, W. H., Teukolsky, S. A., Vetterling, W. T. & Flannery, B. P. (1992), Numerical Recipes in Fortran 77: The Art of Scientific Computing, Second Edition
1992
Cited alongside, same era.

Then

[] Motwani, R. & Raghavan, P. (1995), Randomized Algorithms
1995
Later among the works it cites.
[] Zhao, F. & Guibas, L. (2004), Wireless Sensor Networks: An Information Processing Approach
2004
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…