Two kinds of local

The mean is usually described as global and the median as local. Move one observation far enough and the mean follows it, while the median barely changes.

In a streaming computation, the labels reverse. The mean has a fixed-size representation: map every observation to a pair, add the pairs, and divide at the end.

φ(x) = (1, x)
(n, s) ⊕ (n′, s′) = (n + n′, s + s′)
mean = s / n

Only (n, s) needs to be stored. The familiar update m ← m + (x − m)/n is an equivalent representation that keeps the current mean instead of the sum.

An exact median over arbitrary real values has no bounded-size representation of this kind. A later observation can make an earlier value the new middle, so discarding that value may change the answer.

The first notion of locality concerns perturbing one observation, and the second concerns concatenating two datasets.

Combining partial results

For the mean, each partition returns (count, sum). These states contain everything needed to calculate the mean of the union:

(n₁, s₁) ⊕ (n₂, s₂) = (n₁ + n₂, s₁ + s₂)

Medians do not compose this way. Consider two pairs of partitions:

A₁ = {1, 2, 1000}    B₁ = {-1, 4, 5}
A₂ = {1, 2, 3}       B₂ = {-100, 4, 5}

In both cases, the partition medians are 2 and 4. But the median of A₁ ∪ B₁ is 3, whereas the median of A₂ ∪ B₂ is 2.5. The two partition medians do not record how values from one partition fit between values from the other.

The problem is not specific to storing one number per partition. Any fixed-size exact summary must omit some order information. A continuation can then move the middle rank onto a value whose position was omitted.

A moving rank

Counting observations below a known threshold is streamable:

count += 1[x < 10]

The median asks for the threshold that places half of the observations on either side. That threshold is not known in advance, and its target rank changes as the sample grows.

The fifth-smallest value can be maintained with a heap of size five because its rank is fixed. The median has rank n/2, so the amount of order information required grows with n.

The estimating equations

The mean minimizes the sum of squared deviations. Its stationarity condition is

Σ(xᵢ − θ) = 0,

which reduces to nθ = Σxᵢ. Count and sum are sufficient.

The median minimizes the sum of absolute deviations. Its subgradient condition is

0 ∈ Σ ∂|xᵢ − θ|.

Each contribution depends on which side of the unknown θ an observation lies. Unlike the equation for the mean, this condition cannot be reduced to a fixed set of moments calculated before θ is known.

This also accounts for their different responses to outliers. The mean uses an unbounded but additive residual. The median uses only the sign of the residual, but the point at which that sign changes must be recovered from the ordering of the sample.

Exact and approximate

The restriction applies to exact quantiles. With an error tolerance, a quantile sketch can store an approximation to the empirical distribution in bounded space. KLL and t-digest are common examples.

Database systems expose the same difference. AVG combines across partitions using count and sum. An exact PERCENTILE_CONT must retain enough information to recover the relevant order.