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

Crossing point — where it appears

The parameter value at which two methods cost the same, past which the ordering between them reverses. It is what a comparison of asymptotic classes cannot supply, and quoting it rather than a class is what says whether the better method's advantage has arrived at the sizes anybody runs.

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

1010010³documents in the answeroperations inside the structureevery occurrencerange minimumone descent17 to 324 rows5.14 to 1.94 per document

Work that falls as the answer grows

Output-sensitive usually means the cost rises with the answer instead of with the input. A descent over a document array costs five operations per document at an answer of seven and two at an answer of thirty-two, because the paths to many leaves share their tops.

floors · Index 01e+42e+43e+44e+450100one sampled position in every …bitsplain, one bit a rowcompressed blocksElias-Fano16,384 rowscrosses at one in 4

Twenty bits apart

Two representations of one sparse set, six thousand seven hundred and forty-five bits against six thousand seven hundred and sixty-five. One exploits sparsity and the other exploits runs, and on this set at this density they price identically.

machine · Space binary · sigma 22.00x2 against 4dna · sigma 42.67x6 against 16protein · sigma 204.76x42 against 200latin · sigma 264.81x54 against 26064-position interval2.00x to 4.81x

Two at binary, five at twenty-six

The saving is a factor in the alphabet, so a two-symbol alphabet gets two. Approximate matching in this field is mostly done on DNA, which sits near the bottom of the list at 2.7.

bounds · Symbol 051015204060documents, which here is also the copy countbits a characterFM-indexrun-length indexphrase index8,192 characters throughout2665 runs down to 427

The index that does not notice

Three compressed indexes over the same characters. One is flat at six and a half bits a character however many copies the collection holds; the other two fall by factors of five and six. At one copy the two that fall are the largest of the three.

indexes · Document prose, many short documents4.31 most frequent3.07 drawn from a documentone copy per document5.75 most frequent1.81 drawn from a documentcopies cut across the boundaries5.81 most frequent1.88 drawn from a documentoccurrences per document holding the pattern16 documents · 6-character patternsall three within a tenth on the drawn pattern

One copy per document is one occurrence per document

The output-sensitive listing apparatus wins when a pattern occurs far more often than it occurs in documents. A collection of versions was supposed to be that case, and it is the one collection where the two numbers are equal by construction.

wrong · Document 01e+42e+43e+44e+450100one sampled position in every …bitsplain, one bit a rowcompressed blocksElias-Fano16,384 rowscrosses at one in 4

Where the sparse representation loses

At every row marked, Elias–Fano costs twice the plain vector. The crossing is at one row in four, which is a sampling rate a real index uses — so the choice between the two is a choice, not an improvement.

wrong · Space 10010³10⁴10³10⁴10⁵characters of textoperations, construction includedcrosses at 256the NFAthe DFA64 DFA statescrosses at 256 characters

Where the table starts paying

Five thousand and sixty-five operations before the first character, then one per character. Against nothing before the first character and thirty-nine per character. They cross at two hundred and fifty-six characters, and that crossing is what an engine's compile decision actually is.

practice · Automaton 10100states the cache holdsoperations a characterthe plain NFA: 52.5the whole set fits: 19.94,096 characters · k = 8the knee is at 512 states

A cache below the reachable set

A lazy machine with a cache of two hundred and fifty-six states costs fifty-one operations a character and a plain non-deterministic simulation costs fifty-three. At five hundred and twelve it costs eleven. The line is flat across two orders of magnitude and then falls off a cliff.

wrong · Automaton

Named alongside it

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

Index sizeWavelet treeAutomatonDescentDeterministic automatonDocument collectionDocument listingElias fanoLazy constructionOutput-sensitiveRange minimumRank

All concepts