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

Composition — where it appears

Whether two savings applied together are worth the product of their separate factors. They are when they remove different work and are not when one's removal contains the other's, and the question is answerable from what each removes rather than from how large each is.

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

queries answered yesabsent key, the AND0.190%absent key, built on the intersection0.025%in one set only, the AND1.800%in one set only, built on it0.000%bits set: A 6,351, B 6,294, AND 3,232, direct 1,859no common key is ever denied

The intersection two filters cannot report

Two Bloom filters over sets that share five hundred keys, ANDed bit by bit. The result never denies a shared key, and it looks like a filter of the intersection. It is not one — a key in only one of the sets passes it 1.8% of the time where a real filter of the intersection passes none, and reading the intersection's size off its bits gives 900.

randomness · Randomness a loop over the alphabet1,478,400the compound walk, inside the loop134,40011xone descent per node18,91678x6 patterns · 1 error · sigma 2155.8% of the extensions were dead

Three savings on one structure

A factor of eleven on an extension, a factor of seven on a branching search, and a sixth of the bits. Applied to one bidirectional index they do not give a factor of seventy-seven, and the reason is that two of the three are the same saving.

indexes · Distance factor against the published loopthe compound walk11xthe enumeration78xthe two, multiplied860xnothing measures thisan index with both78xthe shortfall is 11x, and the walk's factor is 11x6 patterns · 1 error · sigma 21the larger of the two, not the product

Two factors that do not multiply

Eleven times and seventy-eight times against the same baseline, so an index with both should be eight hundred and sixty. It is seventy-eight, and the shortfall is eleven — the first factor, exactly, because the second operation already contains it.

wrong · Distance

Named alongside it

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

Bidirectional indexCompound walkInterval symbolsApproximate membershipBacktracking searchBloom filterCardinalityCheckEstimatorFalse-positive rateHash functionIndex size

All concepts