Algorithms & Data Structures
the bound is a claim, and it is checkable
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 6 essays across 2 fields — each of them below, with the objects they name alongside it.

10³10⁴10⁵10⁶passes over the datapeak bits of stateone pass, exact: 1,048,576 bitsradix, uniformsample, uniformradix, paretosample, paretoevery point exact · 32,768 values320 bits at best

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 01234,09616K64K256K1.00M4.00Mmemory in 32-bit words, both buffers included (logarithmic)blocks moved ÷ blocks in the file3 passes2 passes1 passreread the file every passwrite the interval out everypass4,194,304 keys, block 1,024 wordstwo passes from 4,096 words

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 020405101520queries answeredfile-equivalents read and written, in allevery query from nothingthe counts keptparts of equal widthparts the counts balanceuniform keys, 2²² keys, 8K wordsevery answer checked against a sort

A file written once for the queries after

An exact selection against a file of four million keys counts the whole file into a thousand or more pieces on its first pass, keeps the one piece holding its rank, and throws the rest away. Kept, those counts save every later query one full read of the file, from the second query on. Written out as parts, the file makes each later query read a fraction of it — but a pass that counts 3,582 pieces can write only seven, because each part needs a buffer. On a heavy tail, parts of equal width never pay; parts cut where the counts say the keys are pay by the second query and bring twenty-three selections from 69 reads of the file to 9.

bounds · Pass 50%30%10%3%1%0.050.10.20.512share of queries outside the top 2% of rankscost over parts balanced by keysbalanced by past queriessize × queries equal(∫√q)², predictedseven parts, fifty past queriesdotted: parts balanced by keys

Parts cut where the questions are

A file of four million keys, written once as seven parts so that each later selection reads only its own part, can be cut where the keys are or where the questions are. When nine queries in ten ask about the top 2% of ranks, parts balanced by keys cost 1,170 block transfers a query. Parts that each serve an equal share of past queries cost about as much, and a little calculus says they must, on average. Parts cut so that each one's size times its share of queries is equal cost 290, which is the optimum's square-root law, measured to within a third at every concentration tried. The saving lasts exactly as long as the questions stay where they were counted: moved a percentile and a half, the fitted parts cost more than the plain ones.

bounds · Pass 0.020.050.10.20.530050010³10³drift, percentiles every 100 queriestransfers a querya band that never moves, 356best fixed interval, chosenafterevery 1,000 queriesthe law, half-life 250the law, half-life 1,000four streams of 20,000 queries a speedrewrites included

A recut the law decides

Parts of a file cut by the square-root law where selection queries fall lost their advantage once the queries moved a percentile and a half. A partition that recuts itself when the law says the saving pays for the rewrite was predicted to stay within 20% of the best fixed recut interval at every drift speed, and to fail on traffic that jumps. With recent queries decayed at a half-life of 250, it stays within 7% up to a drift of 0.1 percentiles every hundred queries and within 22% at five times that. On jumping traffic it beats every interval fixed in advance, rewriting 13 times a stream where the best interval rewrites 80. The law does not remove a setting: it trades the interval, which has to move fourfold with the speed, for a half-life that does not.

bounds · Pass 0%25%50%75%100%05,00010,00015,00020,000queriesrank in the filethe band's centrethe six cutsone stream, drift 0.1a cut is drawn at each recut

Every cut the law moves

A file cut into seven parts by the square-root law, and recut when the law says the saving pays, was charged a full rewrite for every recut. Charging only the parts whose boundaries change was predicted to cut a recut's cost to a tenth on slow drift. It cuts it by 2%. When the band of hot queries moves, the law moves 98% of its cuts, a median of nineteen thousand ranks each, because the parts on either side of the band have to share out what the band left. Holding small moves back keeps a quarter of the file and costs more a query; recutting only the parts around the band costs up to three times as much.

bounds · Pass

Named alongside it

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

Honest limitSelectionTrade offBlock transferMeasurementHeavy tailWorkloadMulti-passSamplingState bitsStreaming modelComplexity class

All concepts