pith. machine review for the scientific record.
sign in

arxiv: 0806.3301 · v2 · submitted 2008-06-20 · 📊 stat.CO · cs.DS· stat.AP

Fast computation of the median by successive binning

Ryan J. Tibshirani This is my paper
classification 📊 stat.CO cs.DSstat.AP
keywords medianalgorithmdatarunningtimewhenaddedalgorithms
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Divide and Discard: Fast Tightening of Guaranteed State Bounds for Nonlinear Systems

    eess.SY 2026-04 unverdicted novelty 5.0

    A subdivision-and-early-discard strategy tightens guaranteed state bounds for nonlinear discrete-time systems with quadratic complexity and outperforms prior methods on benchmarks.