Concept

Expected cost — where it appears

The cost of a policy averaged over the inputs it will meet, each weighted by how often it arrives. Comparing two policies by it is sound; computing it as a product of averaged parts is not, when the inputs that reach a costly step are the ones for which the step costs most.

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

A match decided by a number

Rabin–Karp replaces a comparison of two strings with a comparison of two integers, and pays for it only when the integers agree by accident. On 65,521 windows at a modulus of 1,009 it verified 79 times against a predicted 64.9. On a text of 1,024 characters chosen with the modulus in hand it verified at 64 windows out of 64 possible, each one costing fifteen of the pattern's sixteen characters — and the closed form is silent about that, because it assumes nobody chose the text.

randomness · Symbol

A second try before any feature

A nearest-word search that learned one starting bound for a whole stream was proposed a bound for each query instead, read off features the search can compute before it walks. The proposed feature separates nothing: 58% of misspelt vocabulary words and 53% of words the vocabulary lacks begin with a real three-letter prefix. Length and unseen letter-triples do predict distance, and still buy about 1%, because the best start is two for almost every class. What closes half the gap to an oracle is a second cheap walk: one, then two, then discover.

tables · Table

Named alongside it

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

Adversarial input Closed form Cost model Edit distance Hash collision Lower bound Measured count Modulus Pattern matching Prediction Pruning Randomised algorithm

All concepts