Computing the median of a large dataset efficiently, particularly in terms of memory usage, is a common challenge in data processing and analysis. Traditional methods, like sorting, are impractical for very large datasets due to their memory requirements. This article explores more memory-efficient methods and provides technical explanations and examples.

Importance of Memory-Efficient Median Calculation

In data analysis, the median serves as a valuable statistical measure of central tendency, resistant to outliers compared to the mean. However, when dealing with large datasets, storing and sorting the entire dataset in memory becomes infeasible due to memory constraints.

Techniques for Memory-Efficient Median Calculation

1. Streaming Algorithms

Streaming algorithms process data in a single pass, using sub-linear memory. They are particularly useful when data cannot fit into memory:

Reservoir Sampling

• Description: Maintain a random sample of fixed size from the stream.
• Memory Use: Constant space, as only a fixed-sized sample is stored.
• Pros and Cons: Efficient and simple; however, provides an approximation rather than the exact median.

Count-Min Sketch

• Description: Probabilistic data structure that offers frequency estimates.
• Memory Use: Sub-linear space.
• Pros and Cons: Effective for frequency-related queries but not directly for median calculation.

2. Online Median Algorithm

The online or incremental median algorithm maintains two heaps:

• Min-Heap: Keeps track of the larger half of the data.
• Max-Heap: Keeps track of the smaller half of the data.

Implementation Steps:

1. Initialize two heaps: a max-heap for the lower half and a min-heap for the upper half of the dataset.
2. For each new element:
   • Decide which heap to insert into based on the element's value.
   • Balance the heaps if necessary (heaps should be approximately the same size).
3. Median determination:
   • If both heaps contain an equal number of elements, the median is the average of their top elements.
   • If they differ in size, the larger heap's root represents the median.

Example Code (Python):

• TDigest: Useful for summarizing large-scale data while estimating quantiles like the median.
• Quantile Sketches: Provide fast, memory-efficient quantile approximations with controllable error bounds.