How to choose data for median estimation: sequential pass or random subsampling?

The choice between a sequential pass and a random sub-sampling for median estimation depends on the data volume and accuracy requirements.

• Sequential pass (single-pass algorithm) is suitable if the data can be processed entirely and there is an option to store it or use memory-limited algorithms (e.g., heap-based or streaming algorithms for median). This approach provides an exact result but can be time-consuming and memory-intensive for large data.

• Random sub-sampling is used when the data is very large and a full pass is impossible or too costly. A random sample is taken from the data, on which the median is computed. This is faster, but the result is approximate, and the accuracy depends on the sample size and data distribution.

In practice, a hybrid approach is often used: first, a random sub-sample to estimate the median with acceptable accuracy, and if necessary, more precise methods on smaller subsets of data.