Every essay — page 6
What a bound is Counting The floors What the machine does Structures Two parameters The other axis When the algorithm flips a coin What the libraries do When it does not fit One pass, and no room The data that is not a number When the algorithm is a table The index that replaces the text What is taught wrongly Ladders Objects Search
Two parameters
A graph's cost is in V and E, so no bound here is a comparison until the density is stated. The same two algorithms change places when only the shape of the graph changes.
Where two searches should stop
Search from both ends of a shortest-path query at once and the two frontiers meet somewhere in the middle, having expanded about two thirds of what one search would. Stop at the first vertex both searches have finished, and on five of forty weighted grids the path returned is longer than the shortest. The rule that is always right stops on a different condition, and on one of those grids it also stops sooner.
A bound right for the wrong reason
Orient every edge of a graph towards its higher-degree endpoint and count triangles among out-neighbours, and the work is O(E·d), where d is the graph's degeneracy. The usual reason given is that the orientation keeps every out-degree at most d. On a graph of 1,024 vertices with degeneracy four, 136 vertices have more than four out-neighbours and one has seven. The bound survives by a different argument, and the orientation that does keep every out-degree at most d does less work.
Two estimates that must agree
Run A* from both ends of a query at once, each search guided by its own straight-line estimate, and stop by the rule that is correct for two-ended Dijkstra. On 40 weighted grids it expands 1,002 cells on average and returns a longer path than the shortest on 12 of them. Give both searches one potential, half of one estimate minus half of the other, and the same rule is correct again — on all 40 grids, for 1,041 cells. Two estimates that measure different things cannot share a stopping rule until they are made to measure the same thing.
One Bellman–Ford buys every Dijkstra
A directed graph of 256 vertices with a third of its arcs negative needs shortest paths between every pair. Running Bellman–Ford from every source costs 25.8 million counted operations on the densest graph drawn; running it once, repricing every arc by what it found, and then running Dijkstra from every source costs 13.1 million, and the one Bellman–Ford is under one per cent of that. Floyd–Warshall's 16.8 million is never the cheapest count on the plate. On the sparsest graphs the repeated Bellman–Ford wins, because its early exit makes nine passes rather than 255.
Where the landmarks stand
Four tables of exact distances, each from a chosen cell, turn a straight-line estimate that barely helps on rough terrain into one that cuts a search by a factor of six. Averaged over 1,200 queries on eight maps, the same four tables expand 126 cells a query when their cells are the map's corners and 423 when they are near its centre. The standard choice, each landmark as far as possible from the ones before, expands 141 and loses to the corners on all eight maps. Moving four landmarks to the right places buys more than doubling their number.
What the queries know that the map does not
A greedy rule that chooses landmark cells by rerunning a sample of past queries needs two hundred of them to draw level with a rule that reads only the map — and what it finally chooses, on map after map, is the four corners. Give the queries a destination instead of scattering them, and twenty are enough to beat the corners by 29% on eight maps out of eight. A query log is worth reading exactly to the extent that it is not uniform.
A stop that is correct and never sooner
A two-ended search can stop when the two frontiers' keys together reach the best route found, and it can also stop when either frontier's own estimate reaches it alone. Both rules are safe, so a search may use whichever fires first. On forty weighted grids the second never fires: at the moment the first one stops the search, the larger of the two own-keys stands at 64% of the route. The extra rule costs 60% more counted work and a second priority queue to find that out.
How long a reweighting stays true
Johnson's one Bellman–Ford run costs under one per cent of an all-pairs computation because it is divided over every source. Asked one query at a time it is divided over nothing, and it still repays itself after 2.7 queries — because the preparation is one Bellman–Ford and every query saves a third of another. What decides the trade is not the query count but whether the graph holds still: at half a per cent of arcs redrawn between queries the stored potential is worth exactly nothing, and its life is geometric at a per-arc failure rate of 6.6%.
A potential mended where it broke
A stored reweighting on a 256-vertex graph with negative arcs costs 10,045 relaxations to rebuild, and rebuilding it every time an update breaks it stops paying once half a per cent of arcs change between queries. Mending it from the arcs that broke costs 16 to 442 relaxations instead, and the stored potential stays at two thirds of the per-query cost at every rate of change. When the change is a vertex whose costs all move together, a repair reaches nearly every vertex. It still costs a third of a rebuild.
A placement after the traffic moved
Four landmarks fitted to twenty queries that all end at one cell expand two thirds of the corners' cells there. Move the destination ten cells and the advantage is gone; move it thirty and the fitted placement expands nearly twice the corners' cells. Choosing again costs 317,000 cells of search — the saving of 8,600 queries — so on streams whose destination drifts, a policy that refits on a counter never beats fitting once and keeping the result, and past a drift of about ten cells nothing fitted beats the corners.
A refit that changes one landmark
Choosing four landmarks again after traffic moves costs hundreds of thousands of cells of search, and on drifting streams it never paid. Keeping three and re-choosing the fourth costs a fifth as much — 0.19 of a full selection, not the twelfth the earlier page guessed. On drifting streams, refitting on the counter goes from a loss of up to 13% to within 2% of fitting once, and it wins where the destination moves six cells. When the destination jumps, it is the cheapest policy measured, 12% under the corners at one jump in 10,000 queries — unless the jumps come as often as one in 2,500.
The candidates near where the queries end
Re-choosing one landmark after the traffic moves tried every candidate as the replacement, and most of them could not win. Tried only on the four candidates nearest the new destination, the refit costs 0.085 of a full selection — the twelfth an earlier page guessed — against 0.236, and its placements serve fresh queries within 3% as well. Where the full search's winner lies further away, the refit was barely worth making. A refit that cheap still cannot follow a destination that jumps every 2,500 queries; what holds the counter back was never the refit's price.
Starting from the corners
A landmark search that refits one landmark when its traffic moves lost to the fixed corners when the destination jumped often, and the accounting blamed the one full selection every refitting policy makes at the start. Starting from the corners instead, and never selecting in full, closes 82% of that gap at one jump in 2,500 queries and is the cheapest policy of all at one in 5,000. It gives the full selection back its advantage when jumps are rare, and on traffic that drifts a step at a time it gives up fitting altogether. Its counter fires when the cost rises, and from the corners concentrated traffic raises nothing: the corners are no worse for it, only no better.
A refit priced before it is made
A landmark placement that starts at a maze's corners and refits one landmark when a counter sees recent queries getting dearer closed most of its gap on traffic that jumps — and on traffic that drifts it never fired, because from the corners concentrated traffic raises no cost. The chance it missed is cost that could fall. Pricing that chance directly — the current placement on the last twenty queries against four nearby candidates, every two thousand queries, refitting when the estimated saving pays for the refit — costs 120.5 cells a query at one jump in 2,500 against the counter's 128.9 and the corners' 126.8, and 107.4 on a slow drift against 103.3 for a full selection fitted once. It fails where jumps come every thousand queries, and on one stream it stops firing after its placement has aged.
A horizon the stream can supply
A watch that refits a landmark placement when an estimated saving pays lost where traffic jumped every thousand queries, because its estimate assumed each saving would last a whole window. The horizon proposed to correct it, learned from the intervals between the watch's own refits, is the window every time: the watch looks once a window, so its refits are never closer together than one. A horizon learned from the traffic instead — how long it stays within ten cells of one destination — is safe on every stream and saves 3.4% at one jump in 2,500. At one in 1,000 it reaches 150.7 cells a query against the corners' 142.7, and a horizon read from the future only ties them. At that pace the looking costs what the refits save.
A watch that looks less
A landmark watch that refits when an estimated saving pays loses to the plain corners when traffic jumps every thousand queries, because its looking costs more than its refits save. Using its learned horizon to look less often there — doubling the interval when the horizon falls below half of it, halving it when the horizon comes back — was predicted to tie the corners at that pace and cost nothing elsewhere. It ties nothing: 150.5 cells a query against the corners' 142.7, since the looks it skips are the looks that found the chances. And at one jump in 2,500, where the watch had won, it loses by twenty cells, because the rule cannot come back down. Halving needs a horizon as long as the stretched interval, and at 8,000 queries no stream here supplies one. A two-state rule that can come back does better and still loses at both paces. The looking was never the waste; at one jump in 1,000 there is nothing to watch for.
A watch that switches itself off
A landmark watch that cannot beat the plain corners by looking less was given a switch instead: at every look it prices the corners on the same twenty queries, and when the corners would have been cheaper over its last four looks it goes back to them and stops looking for 8,000 queries. At one jump in 1,000 it works — 145.5 cells a query comparing search costs, 144.4 charging the watch for its own looking and refits, against the corners' 142.7 and the watch's 150.7. At one jump in 2,500, where watching pays, both switches give the watch's advantage away, 125.3 and 126.1 against 116.4, and the charging switch is off for 60% of the stream, as much as at the fast pace. What a look reads is the same at both paces: 12,249 cells a window at one, 11,257 at the other, with a spread of sixty thousand. The watch's value arrives in a few large looks after jumps, and four looks at any pace are mostly the others.
A switch that counts the jumps
A landmark watch whose switch read its own costs could not tell fast traffic from slow, because what a look reads has the same mean at both paces. A switch that reads the traffic instead — the mean spacing of the last ten times the destination moved more than ten cells — was predicted to reach the corners at one jump in 1,000 and keep the watch at every slower pace. It separates the paces where costs could not: 146.6 cells a query at one jump in 1,000 against the watch's 150.7, and on drifting traffic it never switches off at all. But a count of k events is a reading with a delay of k events and a noise of one part in √k, and no k has both: three stretch ends reach the corners' 142.7 at the fast pace and are off 38% of the slower stream; twenty never misfire and save nothing. And when traffic slows, the events that would show it stop arriving, so the count keeps its fast reading and the switch stays off: 135.8 cells a query on a stream that slows halfway, worse than the corners or the watch.
A switch that hears the traffic stop
A landmark watch switched off by a count of the traffic's stretch ends cannot see traffic slow down, because a slowing is the events stopping, and a count of events keeps its last reading. Letting the open spacing since the last stretch end into the reading, once it is longer than the recorded ones, was predicted to turn the watch back on within four thousand queries of a slowing and cost nothing on steady traffic. It costs nothing on steady traffic, and on ten stretch ends it hears the slowing late, after three to eleven thousand queries, because the silence is averaged with nine fast spacings. On five or three it hears it in time, and the switch on five comes within two cells of the best known policy on every stream.
A silence that overrules the count
A landmark watch switched to the corners by a count of the traffic's stretch ends heard a slowing only once the silence outweighed the fast spacings it was averaged with, about 5,900 queries on ten stretch ends. Letting an open spacing of 1,600 queries overrule the count outright was predicted to make the count's length stop mattering on the stream that slows. It hears the slowing within a thousand queries at every count from three to ten, and keeps the corners 8% of the slow half where the count kept them 65 to 75%; the counts still differ, by 3.4 cells a query, because the fast half is where a short count keeps the corners that pay. On the stream that speeds up the override is the cheapest switch at every count, and on steady traffic it is within a cell and a half of the silence.
A gap between off and on
A landmark watch switched to the corners whenever a count of the traffic's last stretch ends read under 1,600 queries, and back on when a silence of 1,600 overruled the count. A count that only decides when traffic is fast need not use the silence's threshold, so a second, lower one was given it: keep the corners only once the count reads under 1,200. At one jump of the destination in 2,500 queries, on three stretch ends, that saves 3.5 cells a query — 117.8 against the override's 121.3 — but keeps the corners 13% of the time, not under 5%, and stays 1.4 cells above the watch rather than within one. At one jump in 1,000, where the corners are right, the gap costs 1.7 cells; on five stretch ends it saves nothing anywhere; and at slower paces, on traffic that changes pace and on drift, it changes nothing. The two jobs do want two numbers, but only one count length wants them.
A margin the count sets itself
A landmark watch switched to the corners when a count of the traffic's stretch ends read fast saved 3.5 cells a query at a moderate pace once given a second, lower threshold for switching off — but only on a count of three, and at a cost at the fast pace. A fixed gap is the same at every count, so the gap was set by the count instead: switch off only when the reading plus Z of its own standard errors is under 1,600. At one standard error on three stretch ends it makes exactly the fixed gap's choices, 117.8 cells a query at one jump in 2,500 and 144.5 at one in 1,000 — losing 1.9 to the override at the fast pace where under one was predicted, because fast spacings are bunched, not similar. Averaged over six streams every switch on three or five stretch ends lies within about a cell and a half of the best, 113.8: the off threshold, however it is chosen, trades the moderate pace against the fast one, and the count's length decides more than its margin.
The index that replaces the text
Every index measured here before this one was weighed at zero. A suffix array is four times the size of what it indexes and cannot answer without it; a compressed self-index is a third of it and hands the text back on request. The unit is the bit, the primitive is a rank on a bit vector rather than a comparison of two characters, and the text is taken away before any query is allowed to run.
An index larger than what it indexes
A suffix array over 16,384 characters is 229,376 bits, and it cannot answer a single question without the 81,920 bits of text beside it. Nearly four times the text, to search the text. Every index on this site had been weighed at zero until somebody put one on a scale.
A search that runs backwards
Twenty-three occurrences of a six-character pattern in sixteen thousand characters, found in twelve rank queries and zero character comparisons. Not few comparisons — none. The algorithm never asks whether two symbols are equal, and it knows how many matches there are before it has located one.
The index that is smaller than the text
The Burrows–Wheeler transform is a permutation, so it changes no symbol frequency and a plain index over it is the same size whether the text has deep structure or none — 6.29 bits a character against 6.16, on texts whose third-order entropies differ fourfold. What the transform changed was the runs, and a structure that charges one bit per bit cannot see a run.
The sampling that goes the other way
An FM-index hands the text back, and the way it does it is to walk from the last character to the first. So thirty-two characters from the end cost thirty-three steps and thirty-two characters from the beginning cost eight thousand one hundred and ninety-two. The repair is a second array the same size as the first, indexed the other way round.
The index that stores the runs
A compressed self-index over thirty-two copies of a text is 30,557 bits, because its size follows an entropy that cannot see a copy. An index that stores the transform as its runs is 11,900 — and at a single copy it is the larger of the two, which is what makes the comparison a claim about repetition rather than about size.
The sampling that follows the runs
A run-length index over thirty-two copies of one text spends 11,286 bits on its suffix-array sampling and 5,605 on the transform it was built to compress. Sample at the run boundaries instead and the sampling is 10,942 bits that stop moving — two values per run, and a function that fills in everything between them.
The occurrence carried through the search
Backward search returns how many and not where, and every index on this site pays for the second question separately. Carrying one occurrence along with the interval costs a lookup on 75% of the steps for a two-character pattern and on 18% of them for a sixteen-character one, and it is what makes a run-boundary sampling usable at all.
An index with z in its size
Over thirty-two copies of one text, an index built on the parse is 8,892 bits, the r-index is 17,047 and the entropy-bounded index is 34,615. Over eight thousand characters of four-symbol text the same three are 7,844, 25,177 and 20,413, and the smallest of the three has changed places twice.