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

Descent — where it appears

A walk from a wavelet tree's root that carries an interval and splits it at every node, entering a child only when its half is non-empty. It costs two bit-vector ranks per internal node entered, and the nodes it enters are exactly the ancestors of the symbols the interval holds.

Named by 11 essays across 7 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 0100200300102030distinct symbols in the intervalbit-vector ranksthe loop: 320the descentsigma = 32 throughout32x down to 5.16x

Proportional to the answer, not the alphabet

At a fixed alphabet of thirty-two, a loop costs three hundred and twenty ranks whether one symbol is present or all of them. The descent costs ten and sixty-two. The experiment has to move the answer without moving the alphabet, and the obvious sweep moves both.

floors · Symbol acdefghijklmnopqrstuvwyzroot24 of 26 symbols present54 ranks · 51 nodes

A node costs two ranks

The left child's interval is the position minus the right child's. A descent that calls rank on both children returns exactly the same symbols at twice the cost, and nothing about the answer can see it.

machine · Symbol 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 every occurrence5610 documentsrange minimum and chain32510 documentsrange minimum, no chain9610 documentsone descent over D3810 documentsthe document arraythe document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree56 occurrences in 10 documentsoperations inside the structure

The tree answers the question

The distinct documents in a range of rows are the distinct symbols of the document array in that range. A wavelet tree enumerates those in one descent, so the range minimum, the chain, the bitmap and the recursion all go at once.

indexes · Index acdefghijklmnopqrstuvwyzroot24 of 26 symbols present54 ranks · 51 nodes

Asking about symbols that are not there

A search extends an interval by every character of the alphabet, and on a deep branch almost all of them produce an empty interval. That is a full rank walk whose entire result is the discovery that nothing was there.

indexes · Symbol bits heldbalanced49,593huffman41,589the answer comes backbalanced: sorted · 26 operationshuffman: sorted · 24 operations32 documents · zipf lengths83.9% of the ordered tree

The smaller tree hands it back unsorted

A frequency-shaped tree is sixteen per cent smaller and returns its documents in code order. A balanced one is larger and returns them sorted. The trade is d log d comparisons against a saving, which is not close — until the answer is truncated.

practice · Index extensions attempted9,206 dead7,594 livebit-vector ranksthe loop: 168,000the descent: 24,0868 patterns · 1 error · sigma 2054.8% dead · 6.98x

The branches that find nothing

An approximate search over a twenty-symbol alphabet attempts sixteen thousand eight hundred extensions and nine thousand two hundred of them produce an empty interval. That is a full rank walk whose entire result is the discovery that nothing was there.

structures · Symbol 02040608000.50011.502errors permittedbranches that find nothing, per cent5.75x6.98x9.22xthe label is thesaving at that budget8 patterns · 8 characters31.3% to 74.9%

A looser budget wastes a larger share

More errors permitted means more work, and the fraction of that work which was never going to help rises with it — from thirty-one per cent at no errors to seventy-five at two. The saving is worth most where the search is most expensive.

practice · Symbol a fixed-length codeleaves in order␣acdefghilmnoprstuvwythe best ordered treeleaves in order␣acdefghilmnoprstuvwythe best tree of any shapeleaves in frequency order␣eahnrstdiloucfgmpvwythe symbols, in the order the descent reports them21 symbols in 2,048 positionsone set, 2 of 3 sorted

One set, three orders

The symbols an interval holds do not depend on the tree's shape. The order they come out in does, and a search that accumulates a running count as it reads them computes a plausible number that is wrong on eighty per cent of queries.

wrong · Symbol acdefghijklmnopqrstuvwyzroot24 of 26 symbols present54 ranks · 51 nodes

A walk that does not prune

Remove the emptiness test and the descent visits every node of the tree, returns exactly the same symbols with exactly the same intervals, and costs sixty per cent more. No test of the answer can see it.

wrong · Symbol

Named alongside it

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

Wavelet treeInterval symbolsRankAlphabet sizeBacktracking searchCheckDead branchDocument arrayDocument listingCorrectnessCrossing pointError budget

All concepts