Concept

External-memory — where it appears

A model in which data sits in a large slow memory read in blocks of B items through a fast memory of M items, with cost counted in block transfers. It is the model in which a pass over a file costs n/B and a buffer costs a block.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

What a second pass buys

Exact selection of a median from thirty-two thousand values needs the whole stream in one pass — a million bits — and eleven thousand in two. By nine passes it is three hundred and twenty. The state falls as n to the power one over p, which is a law with an exponent worth fitting, and on skewed data the deterministic rule misses it by three orders of magnitude.

space · Pass

What a pass costs when it is a file

The streaming model trades passes for memory along n to the power one over p, and it never says what a pass costs. On a file a pass is a read of every block, and it cannot run in less than one block of memory. Charge both and the trade nearly disappears: the median of four million keys takes three passes at two blocks of memory and two passes at four, and writing the surviving interval out makes the third pass cost sixteen blocks instead of four thousand. On a heavy tail the same habit nearly doubles the bill.

bounds · Pass

Named alongside it

The objects these essays reach for when they reach for this one.

Heavy tail Honest limit Measurement Multi-pass Sampling Selection State bits Streaming model Trade off Block transfer Complexity class Fitting

All concepts