HackerPapers

arXiv:0806.3301stat.CO

Fast computation of the median by successive binning

Ryan J. Tibshirani

HN submission. Found in a submission link or body. Submitters do not count as commenters in the main ranking; a submission is not an endorsement.

Abstract

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.

arXiv comments
14 pages, 1 Postscript figure
Journal reference
DOI
Subjects
stat.COComputation (Statistics) cs.DSData Structures and Algorithms stat.APApplications (Statistics)

On Hacker News

No comments linking this paper were found in the collected sources. Found in 1 HN submission from Jun 2008 to Jun 2008. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments0 threads

No comments linking this paper were found in the collected sources. Open submission discussions.

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.