Landmark — where it appears
Named by 10 essays across one field — 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.
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 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.
Named alongside it
The objects these essays reach for when they reach for this one.
Break-evenHeuristic searchPreprocessingShortest pathParameter choiceQuery distributionHonest limitSamplingRegimeTriangle inequalityAdmissibilityGreedy