Break-even — where it appears
Named by 21 essays across 5 fields — each of them below, with the objects they name alongside it.
An estimate borrowed from an easier problem
On a grid where every step costs one, the straight-line distance to the goal cuts a search from 543 cells to 325. On terrain where steps cost between one and nine it cuts 1,572 to 1,550, because it still believes every step costs one. Four exact distance tables, computed once, cut the same search to 252 — and cost 6,328 reads to build, so they pay for themselves on the fifth query.
The index that is the text
A suffix array sorts all 4,097 suffixes of a text — 8.4 million characters of string, in total — and examines exactly zero characters doing it. It then answers a search in 91 characters where a scan costs 1,472, and the whole thing pays for itself at six queries. Both halves of that are worth the same amount of attention, and the first is the one that is usually skipped.
What a planner pays to find out what to pay
Insurance against a row estimate is set from the error's median and spread, and a running system knows neither — it has to fit them from executed queries. Fitted from one query the divisor costs 1.263 times the better plan against 1.215 for a planner that never insures at all, so learning is worse than not learning until about sixteen queries have run. The tail, though, is bought immediately: one observation already holds the worst case to 24.7 against 36.6.
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.
The price of remembering an answer
Give selection sort a table of the pairs it has already compared and it makes 16,805 comparisons on 256 elements instead of 32,640. The table pays for itself once a comparison costs more than 3.1 word operations, and that price stays near three at every size measured. Give it the full closure of everything its answers imply and it makes 13,079. The closure pays only past 425 operations a comparison at that size, and past 1,659 at twice the size. The cheap memory is worth having on long keys. The complete one is worth having almost nowhere.
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 planner that knows how sure it is
A planner that fits its insurance divisor from a handful of executed queries under-insures, because a spread fitted to a small sample is biased low. The textbook repair is to use the upper end of a confidence interval on the spread instead of its centre. At a read ratio of four it makes the planner worse than trusting its estimate for longer — until sixty-four queries rather than sixteen — and it buys the worst case immediately, from 22.4 times the better plan to 6.2 after two queries. The bound is not a correction towards the truth. It is a dial between two different planners.
The runs a permutation does not leave
A run of length L costs 2⌊log₂ L⌋ + 1 bits and replaces L, so coding runs pays above a mean run of six. This grid's mean run is 2.34, chance gives 1.90, and coding its runs makes it 17.8% larger.
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 pass repaid by the scans after it
Give the two-ended selection sort one pass between neighbours before it starts, n − 1 comparisons, and sorted and reversed keys cost exactly that pass. The pass was predicted to be repaid in the first scan, and almost none of it is. On organ-pipe keys it saves 43,776 comparisons at 1,024 keys, 97% of them in the scans after the first. On random keys it costs 236, not 1,023, because later scans use the short runs it found. It breaks even on runs of four keys at every size — and the sort stays quadratic on every input that is not one run.
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.
The level where compression stops paying
Choosing the best coding for every level of the grid separately, rather than one for all twelve, saves 26 bits out of 47,668 — five hundredths of one per cent. The apparatus for choosing costs more than that to describe.
Named alongside it
The objects these essays reach for when they reach for this one.
Shortest pathHeuristic searchLandmarkPreprocessingParameter choiceHonest limitQuery distributionSamplingPotential functionRegimeSpace time tradeCost model