A refit that changes one landmark

A placement after the traffic moved found that landmarks fitted to one destination lose their advantage within ten cells of it, and that choosing them again is too expensive to be worth doing. A greedy selection of four landmarks from twenty-five candidates re-runs a sample of twenty queries for every candidate in every round. On the maps measured it cost about 317,000 cells of search, the saving of some 8,600 queries at the destination it was fitted to. On streams whose destination drifted, a policy that refitted whenever a counter saw queries getting dearer never beat fitting once and keeping the result, and past a drift of about ten cells nothing fitted beat the four corners.

Its closing section put the blame on the selection starting from nothing. After the traffic moves, not every landmark has gone stale. The selection keeps about one corner on average, a landmark useful to every destination, and it moves the others towards the destination it was fitted to. A refit could keep three landmarks and re-choose one. That section predicted the refit would cost a twelfth of a full selection, that it would pay at drifts where a full refit does not, and that on a stream whose destination jumps rather than drifts, a counter with the cheaper refit would beat fitting once. It flagged the drifting streams as the uncertain part.

Three kept, one re-chosen #

The refit tries each of the four landmarks out once: it drops that landmark, runs the recent sample of twenty queries with the other three, and notes how many cells they expand. The landmark whose loss hurts least is the one to replace. It then tries each of the twenty-five candidate cells as the fourth beside the three it keeps, and takes whichever makes the sample cheapest. The landmark it dropped is one of those candidates, so a refit that finds nothing better leaves the placement as it was.

Every search in that procedure is charged to the policy that asked for it, exactly as the full selection’s searches were. The queries are A* searches on the same weighted 50 by 50 terrain maps as the earlier essay, with distance tables from each landmark. The cost of a query is the number of cells it expands. A policy’s bill is its queries plus every cell its selections expanded.

The incremental refit costs a fifth of a full selection, not a twelfth. The prediction counted the wrong thing. A full selection tries 25, 24, 23 and 22 candidates in its four rounds, 94 trial runs of the sample. The incremental refit tries 4 removals and 22 replacements, 26 runs, which is 28% by that count. Counted in cells it is cheaper still, 19%, because the runs are not equally expensive. A full selection’s first round tries each candidate as the only landmark, and a search guided by one table expands far more cells than one guided by four. Every run of the incremental refit has at least three landmarks in hand, so each of its searches is short. A fifth is still a large reduction, and whether it is large enough depends on how often the refit is needed.

On streams that drift #

The streams are the earlier essay’s. Before each of 30,000 queries the destination steps to a neighbouring cell with a stated chance, and each query starts from a uniformly drawn cell. Five policies see the same queries. The corners never fit anything. Fitted once chooses four landmarks after the first twenty queries and keeps them. The two counter policies watch the mean cells of their last 2,000 queries and refit when it exceeds, by half, the mean they measured just after their last fit: one with a full selection, one by re-choosing a single landmark. The fifth re-chooses a single landmark every 5,000 queries whatever the counter says. Every point is the mean of six maps and walks.

The prediction’s uncertain part came out in the refit’s favour, but only just.

Re-choosing one landmark on the counter turns the counter from a liability into a draw. With a full selection the counter costs 141.5 cells a query at the smallest drift where fitting once costs 124.7: 13% more for having reacted. With the incremental refit it costs 127.3, within 2% of fitting once. Across the four slower drifts it is never more than 2% behind, and at a step chance of 0.003 — the destination ends about six cells from its start — it is ahead, 128.6 against 132.8. On a still stream the counter never fires and all three fitted policies are the same policy.

That is the modest version of the prediction. An incremental refit pays at a drift where a full one does not, and it does so by a few per cent in a band of drift about as wide as the fitted placement’s own advantage. What the queries know that the map does not found the fitted advantage to be about a third of the corners’ cost at the fitted destination, and six cells of drift is where half of it has gone. That is the window in which a cheap correction has something left to save.

At the fastest drift, only the periodic refit is under the corners. At a step chance of 0.03 the destination ends 22 cells from its start. Fitting once costs 171.1 cells a query, the full counter 168.7, the incremental counter 145.3 — all above the corners’ 138.2. Re-choosing one landmark every 5,000 queries costs 128.9, 7% under the corners. The counter fires only about once a stream here, because the cost creeps up as the destination drifts and the counter compares against a baseline measured after its last fit. By the time the drift has pushed the mean up by half, most of the damage is done. A refit on a schedule does not wait to be told.

On streams that jump #

The case the prediction was surest of is a destination that does not drift but jumps. Before each query the destination moves, with a small stated chance, to a uniformly drawn open cell. The jumps come at random times, so no policy’s schedule can line up with them.

That detail is worth stating because the first version of this measurement got it wrong. Its jumps came on a fixed schedule, every 5,000 queries, which is also the periodic policy’s period, so every periodic refit landed twenty queries after a jump with a sample made entirely of queries to the new destination. The periodic policy looked better than the corners, and the reason was the schedule.

On jumping streams the incremental counter is the cheapest policy measured, wherever the jumps are not too frequent. At one jump in 10,000 queries it costs 124.1 cells a query against the corners’ 140.5, 12% less, and against 220.9 for fitting once. At one jump in 5,000 it costs 132.4 against 141.1. At one in 30,000, where most streams see no jump at all and a few see one, it costs 122.3 against the corners’ 163.2.

That last figure shows the corners doing badly on a stream where hardly anything happens, and the cause is the particular destinations: a map’s corners are poor for some destinations and good for others, and at 0.8 jumps a stream the average is over few of them. The fitted policies all start from a placement chosen for the first destination, and at that jump rate the first destination is usually the only one.

Fitting once is the worst policy on every jumping stream. It is above the corners on every jumping stream, by 9% at the slowest rate and by 43% to 57% at the others, because a placement fitted to a destination that has since jumped is not merely stale but actively misleading. That is the earlier essay’s decay plate at its far end: thirty cells away, a fitted placement expands nearly twice the corners’ cells.

The prediction said the incremental counter would beat fitting once, and it does so by a factor of 1.3 to 1.8 at every jump rate. It did not predict that the counter would beat the corners too, and it does, except at the fastest jump rate. At one jump in 2,500 queries the corners win, 133.8 against 156.3. The counter needs 2,000 queries of evidence before it can fire. At that jump rate the destination has often moved again before the refit has been paid for, and the cheapest policy is to fit nothing.

Where the cells go #

The split shows what the incremental refit buys and what it does not. Its queries are cheaper than the full counter’s — 110.0 cells against 115.0 — though each of its refits changes only one landmark. It refits more often, 3.5 times a stream against 2.8. Each refit is cheaper, so the counter’s baseline resets closer to each jump and it fires again sooner. Its selections cost 22.5 cells a query, where the full counter’s cost 36.0.

The selections are still a large share of the bill. At one jump in 5,000 queries the incremental counter spends a sixth of its cells choosing landmarks. The earlier page’s conclusion that choosing is expensive stands; what changes is that a cheaper choice can now be made often enough to follow the traffic. It is the same trade a potential mended where it broke made one layer down, where repairing a stored reweighting from the arcs that broke stayed worth doing at every rate of change and rebuilding it did not.

The single stream shows the counter working and its limit. Its first refit comes 143 queries after the first jump, fast enough that the stale placement costs almost nothing. The next five jumps come within 4,600 queries of each other, and the counter’s window of 2,000 cannot keep up with that: it refits at 7,964, 196 queries after the jump at 7,768, and not again until 14,127, after the destination has settled. At the end of the stream it catches the jump at 26,287 with a refit 1,794 queries later. Over the stream it expands 100.2 cells a query where the corners expand 137.8.

A refit is dearest when it is needed #

The price plate charged an incremental refit on a sample of queries to a fresh destination, with a placement that was reasonable to begin with. In the streams, the refits are charged what they actually cost, and the two policies pay very different prices for the same procedure.

A periodic refit costs 51,000 to 80,000 cells on average, about the price-plate figure. A refit fired by the counter costs 71,000 to 146,000 — at one jump in 5,000 queries, 116,000 against the periodic refit’s 70,000. The difference is when each one runs. The counter fires because the placement has gone badly wrong, so the sample it refits on is a sample of queries the current placement serves badly, and every trial run of that sample is a long search. The periodic refit usually runs when nothing much has changed, on a sample the placement serves well, and its trials are short. A refit is dearest exactly when it is needed, by about two thirds. That is the same shape as the insurance what a planner pays to find out what to pay priced: the information arrives in the case where acting on it is most expensive.

The periodic refit’s cheapness has a second face. On the jumping streams, 9 of its 120 refits found nothing better than the placement it had and kept it. It paid for a search that confirmed the status quo, and on a still stream it pays that price five times a stream for nothing, which is why it sits 5% above fitting once when the destination never moves.

Which landmark does a refit drop? Across the counter’s refits on both kinds of stream, it dropped one of the map’s corners in 16 of 68 — about one in four. The fitted placements hold about one corner in four landmarks, so a refit drops a corner about as often as chance would. The earlier page’s reasoning — that the corners are the landmarks worth keeping — was not what the refit acted on. It dropped whichever landmark the recent sample needed least, and on a sample of twenty queries to one destination, a corner behind that destination is as useful as a fitted landmark beside it.

The arithmetic of a jump #

Whether a counter can follow jumps comes down to three numbers, and each can be read off the plates.

The counter needs evidence before it fires: its window is 2,000 queries, and the mean over that window must rise by half. After a jump, the stale placement’s queries cost about 79 cells more than a fresh placement’s would — the gap at one jump in 5,000 between fitted once, whose queries cost 188.8 on average, and the incremental counter’s, at 110.0. And the refit itself costs about 116,000 cells, so it repays itself after about 1,500 queries of that saving.

So a jump is worth reacting to only if the destination then stays put for the counter’s detection time plus the refit’s payback: roughly 2,000 plus 1,500 queries. At one jump in 10,000 queries the typical gap between jumps is three times that, and the counter is the cheapest policy by 12%. At one in 5,000 the gap is just over it, and the counter wins by 6%. At one in 2,500 the typical gap is shorter than the time a refit needs to pay for itself, and every refit is a bet on the destination staying put for longer than it usually does. The corners, which make no bet, win.

That arithmetic also says what would move the boundary. A shorter window would notice sooner and refit on noise more often. A cheaper refit would repay sooner. The earlier page’s full selection, at about three times the incremental refit’s price in the streams, needs about 5,000 queries of payback on top of detection, which is why it loses to the corners at every jump rate but the slowest. The detection problem is the one what a heavier tail actually buys measured for decayed counters: a detector tuned to stay quiet when nothing is happening takes longer to see something that is.

What the counter still decides #

Everything above keeps the earlier page’s counter: a window of 2,000 queries and a threshold of half as much again. Neither was swept, and both matter more with a cheap refit than with an expensive one — the counter is a threshold on evidence, the kind a planner that knows how sure it is found costs regret whichever way it is set. An expensive refit wants a counter that rarely fires. A cheap one can afford to fire on weaker evidence, and a shorter window would notice a jump sooner, at the price of refitting on noise.

The candidates are the same 25 cells. Each is the open cell nearest a point of a 5 by 5 lattice that includes the corners, as in what the queries know that the map does not, whose estimates are the tables an estimate borrowed from an easier problem improved on. A refit that could choose any cell might find a better fourth landmark; it would also be far more expensive, since the candidates’ distance tables are the one cost this page does not charge, computed once per map and shared by every policy.

The stream plates do not check each query’s distance against the exact one. The price plate’s selections and the decay measurements of the earlier page were checked. The streams run 30,000 queries under five policies on six maps, and computing an exact distance for every one was not affordable. The A* searches use tables of exact distances, which gives an admissible and consistent estimate whatever the placement, so a wrong answer would be a defect in the search rather than a property of the placement. That is the same position as the earlier page, and the same shortfall.

Six maps. At six maps the differences of 2% on drifting streams are within what a different set of maps could reverse. The differences on jumping streams, 6% to 25%, are not.

Where the landmarks stand is the page on what a landmark placement is worth at all, and the corners’ steadiness across every plate here is its result: never the best placement for any one destination, never far from it for any.

Still open: the candidates a refit need not try #

The incremental refit spends most of its searches on the replacement: 22 of its 26 trial runs try a candidate as the new fourth landmark. Most of those candidates cannot win. The landmark being replaced is the one that was useful to the old destination, and its replacement will be useful to the new one — which means it will be a cell behind the new destination as seen from where queries start. The sample of twenty recent queries already says where the new destination is.

The measurement that follows restricts the replacement to the candidates nearest the recent queries’ destinations, the four to eight lattice cells around them, and asks what that does to the price and to the refit’s quality. The prediction is that the price falls from a fifth of a full selection towards a twelfth, which is the figure the earlier page guessed for the wrong reason. It also predicts that the refit loses little, because the candidates it skips are the ones a greedy search rejects anyway. If the prediction holds, the counter can afford a shorter window, and the question the jumping streams leave open — whether a counter can follow jumps a few thousand queries apart — gets a second measurement with a cheaper refit in hand.