Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Per level — where it appears

Accounted separately for each level of a layered structure rather than for the structure as a whole. Allocating memory or error level by level lets the small levels get more of it where it buys the most, which a single setting for the whole structure cannot do.

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

0.020.050.10.20.5121235810filter bits a keywasted reads per absent lookupno filters: all 3 levelssame rate every levelrates sized to levelsn = 65,536, size ratio 4, first run 1,024 keysthe same memory at every point

The filter each run carries

A log-structured store turns every lookup for a missing key into a read of every level, and a Bloom filter on each run buys those reads back with memory. Spread five bits a key evenly across three levels and a missing key still wastes 0.279 reads. Give the small levels more bits and the large one fewer — the same memory — and it wastes 0.201. At four levels the gap is 0.382 against 0.209, because sized filters stop the waste growing with the number of levels.

applied · Transfer 02e+34e+36e+301234567891011level of the wavelet treebitsplainblock-codedrun-coded3,612 points · 12 levels24 copies of 2048 characters

The level where compression stops paying

Choosing the best coding for every level of the grid separately, rather than one for all twelve, saves 26 bits out of 47,668 — five hundredths of one per cent. The apparatus for choosing costs more than that to describe.

wrong · Grid

Named alongside it

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

Trade offBlock transferBloom filterBreak-evenCompressionControlDeferralFalse-positive rateFilteringGridIndex sizeLsm tree

All concepts