Starting from the corners

Where the landmarks stand found four landmarks at the corners of a weighted maze a good placement for any query — an estimate built from four tables of exact distances, which an estimate is a reweighting showed is the same search as a reweighted graph — and a placement fitted to a sample of queries far better for queries like the sample. A refit that changes one landmark kept a fitted placement current as the traffic moved by re-choosing one landmark at a time, fired by a counter that watched the mean cost of recent queries. The candidates near where the queries end made that refit cheaper still, trying only the four candidates nearest the new destination, a twelfth of the price of a full selection. On streams whose destination jumped rarely the cheaper refit won by a wide margin: 80.9 cells a query at one jump in 10,000, against 124.9 for the corners. At one jump in 2,500 it still lost to them, 138.6 against 126.8.

Its accounting found where the loss came from. The refits were cheap and rare; the largest single preparation charge was the one full selection every refitting policy makes at the start of the stream, about 380,000 cells, or 12.6 cells a query over 30,000 queries. The closing section proposed a policy that never pays it. The corners need no preparation and are never far from good, so a policy could start there and use only the restricted refit, fired by the same counter. The first refit would replace one corner with a candidate near the destination, and every later one would replace whichever landmark the traffic valued least. It predicted that saving the first selection would close most of the gap at one jump in 2,500, and named what to try if it did not: keep three landmarks at the corners for good and leave one free to follow the traffic.

The first part holds, on average and not on every map. What the second part was guarding against turned out to be a different problem altogether, one that only traffic of another shape reveals.

Two policies that never select in full #

Both new policies start at the four corners and make no full selection. The corner start watches the same counter as before: when the mean cost of the last window of queries rises by half over its level after the last refit, it fires the four-nearest refit, which drops whichever landmark the recent queries value least. The one free policy keeps three corners for good. Its first refit frees the corner the queries value least, and every later refit replaces only that free landmark. The maps, streams, charges and counter are the earlier pages’, four maps and 30,000 queries a stream, and every search a refit runs is charged. Beside them run the corners alone, one full selection kept for the whole stream, and the earlier page’s counter that starts with a full selection. Every counter policy is shown at its best window of 250, 500, 1,000 or 2,000 queries.

At one jump in 2,500 queries the corner start costs 128.9 cells a query, against the corners’ 126.8 and 138.6 for the counter that starts with a full selection: 82% of the gap closed. The prediction said most of it, and most of it is closed. The counter’s failure at frequent jumps was largely where it started. At one jump in 5,000 the corner start is the cheapest policy measured, 102.2 against 107.8 for the counter with a full selection and 127.2 for the corners. At one jump in 1,000 it is 2% above the corners, where the full-selection counter was 16% above.

At one jump in 10,000 the order reverses. The counter that starts with a full selection costs 80.9 and the corner start 85.1. With jumps that rare, one well-fitted placement serves thousands of queries before it goes stale. A full selection fits all four landmarks to the first destination. A restricted refit changes one, so after its first refit the corner start still has three corners where a fitted placement would have none. The full selection’s 12.6 cells a query of preparation buy a better placement than any single refit reaches, and over long stretches between jumps the better placement repays them.

The one-free policy is within a cell of the corner start everywhere: 128.4 against 128.9 at one jump in 2,500, 84.8 against 85.1 at one in 10,000. The section offered it as the fallback if lateness were the whole problem. It isn’t needed as a fallback, and it does not add anything as an improvement. At every jump rate but the fastest the two make one or two refits a stream, too few for the difference between them — whether a later refit may drop a corner — to arise often. At one jump in 1,000 the one-free policy makes 4.5 refits a stream against the corner start’s 2.0, and ends within a cell of it anyway.

Where the preparation goes #

The counter that starts with a full selection spends 18.4 cells a query on preparation at one jump in 2,500; the corner start spends 1.9. Most of the difference is the selection itself, 12.6 cells a query, and the rest is refits: the full-selection counter makes five a stream and the corner start one and a half. The fitted placement’s cost rises sharply when the destination jumps away from it, so its counter fires often. The corners’ cost moves much less with the destination. On the traced streams its blocks of 500 queries vary with a standard deviation of 39 to 64 cells a query around a mean near 125, where one full selection kept all stream varies by 77 to 150 around a mean near 200. So a counter watching the corners fires only for a jump to somewhere the corners serve badly. Fewer firings mean fewer refits paid for, and at frequent jumps that economy is most of the corner start’s advantage.

One stream shows the mechanism as a sequence of events. The counter that starts with a full selection serves its first 500 queries at 78.3 cells a query, far better than the corners’ 96.8, because it was fitted to the destination those queries share. It has spent 362,526 cells on preparation over the stream, the selection and three refits. After each jump its fitted placement is worse than the corners for a stretch of queries until the counter notices, which is the lateness the earlier page measured. The corner start pays 72,064 cells for two refits. Between refits its cost is the corners’ own, and the stretches after a jump cost it nothing extra, because a placement that was never fitted to the old destination is not worse for losing it.

Map by map #

The mean over four maps hides how differently the corner start fares on each. At one jump in 2,500 queries and a window of 1,000:

The corner start beats the counter that starts with a full selection on every map, but it matches or beats the corners on only three. On the second map it is the best policy by a wide margin, 88.3 cells a query against the corners’ 113.5: there a refit toward the stream’s destinations serves them far better than the corners do, and pays. On the third it never fires, and costs exactly what the corners cost. On the fourth it is 26% above the corners, 174.3 against 138.6. Its counter fires there, and the placements it moves to do not repay their price before the traffic moves on. How long a reweighting stays true asked how long a preparation stays worth what it cost, and on that map the answer is shorter than the gap between jumps.

So the corner start is not a policy that is always at least as good as the corners. It is one that pays far less to be wrong. When it refits badly it loses less than the full-selection counter does, 174.3 against 188.9 on the fourth map, because it never paid for the selection. It does lose, though, and the loss depends on the map as much as on the jump rate. One Bellman–Ford buys every Dijkstra found a preparation worth paying once because every later query shared it. A landmark refit is a preparation of the same kind, shared only by the queries that come before the next jump, and whether it pays is a race between the refit’s price and that interval.

The window no longer decides it #

The earlier page found the window the one thing that could be tuned, and at frequent jumps no window was enough. At one jump in 2,500 the corner start stays between 128.9 and 133.1 cells a query at every window, while the counter that starts with a full selection never gets below 138.6. The window stops mattering because the corner start’s counter fires only for jumps that matter to the corners, which are few, and a window of 250 queries or 2,000 notices them about as well. At one jump in 10,000 both counters want the shortest window. There the corner start at the longest window, 117.8, is back near the corners’ own 124.9: a counter that watches 2,000 queries and waits for a rise by half hardly ever sees one when the placement it watches was never tuned to anything.

A drift that raises nothing #

The section’s prediction was about jumps. The earlier pages also measured traffic that drifts: the destination steps to a neighbouring cell with a small chance each query, so the traffic stays concentrated but moves slowly. There the corner start fails in a way the jump streams do not show.

On a destination that drifts one step in 1,000 queries, the corner start costs 136.7 cells a query, next to the corners’ 139.3, where one full selection costs 103.3. It makes 0.8 refits a stream on average. Its counter fires when the mean cost rises by half over its level after the last refit, and on drifting traffic the corners’ cost does not rise. The traffic concentrates on one region and stays there. The corners serve that region no worse than any other, so their cost holds level while a fitted placement could have cut it by a quarter. A counter is a detector of things getting worse. From the corners, nothing gets worse. It only fails to get better, and no rise in cost can signal a missed chance to fit.

Only at the fastest drift does the order change. When the destination steps with a chance of 3% each query, it moves far during a stream, and one full selection kept all the way costs 195.6 cells a query, far above the corners’ 153.2. The corner start, 139.8, is then better than both. The full-selection counter, which refits as the traffic moves, is best at 131.4. A destination that moves that fast outruns any placement fitted once, and only a policy that both fits and follows keeps ahead of the corners.

That is why the full-selection counter, which lost to the corner start on jumps, wins on slow drift by a quarter, 104.7 against 136.7: its selection is the fit the traffic wanted from the start. The failure is not in the refit or the window. It is in what the counter watches. What the queries know that the map does not found that a placement chosen from past queries needs a couple of hundred of them before it draws level with one read off the map. A corner start never gathers them, because nothing it watches tells it to look.

What was measured and what was not #

Four maps, four jump rates, four windows. Every number is a mean over the same four maps and seeded streams as the earlier pages, 30,000 queries each. The best window is chosen on the streams it is scored on, for every counter policy alike, which flatters all of them equally.

Jumps and drifts, not both. A stream either jumps or drifts, and a policy’s best window was chosen separately for each kind, which no deployed system could do without knowing which kind of traffic it had. Real traffic probably does both, slow drift with occasional jumps, and there the corner start’s two behaviours would compete: cheap answers to jumps, and blindness to drift.

The restricted refit only. Every refit here tries the four candidates nearest the destination. A corner start whose first refit was a full selection would be the earlier page’s policy, fired later; that is a different policy, and it was not measured.

Four maps. The means above are over four maps, and the table shows the maps disagree about the corner start more than about any other policy. Four maps is enough to show that disagreement, not to say how often a map is like the fourth.

Cells, not time. Every cost is cells expanded by a search, preparation included. A placement after the traffic moved measured how fast a fitted placement’s advantage decays with distance from its destination, and the counts here rest on the same measure.

What the counter was built to see #

Both of the corner start’s failures come from the same design choice, made on an earlier page for a different starting point. The counter was built for a placement that had been fitted. For a fitted placement the danger is decay: the traffic moves away and the placement becomes worse than the corners, so a rise in cost is exactly the signal to act on. The counter measures its baseline right after each refit, when the placement is at its best, and fires on a rise by half.

Started from the corners, the same counter measures its baseline on a placement at its most ordinary. A rise by half above the corners’ cost is a rare event, a jump to a destination the corners serve unusually badly, and that is why the corner start refits so seldom and pays so little. It is also why it misses the drift. Concentrated traffic is an opportunity for a placement at the corners, and an opportunity never shows up as a rise. The first counter was a detector of loss, and the corner start needed a detector of gain.

Still open: a counter that watches for a missed chance #

The corner start’s counter can only see cost rising, and on concentrated traffic the chance it misses is cost that could fall. A detector for that needs a comparison, not a threshold: what the current placement costs on recent queries against what a refitted one would cost. The refit’s own search computes the second number, but it is too dear to run on every window just to find out.

A cheap estimate exists. The restricted refit already ranks the four candidates nearest the recent destination, and the cost of the current placement on a small sample against the best of those four, one extra search per candidate, is an estimate of the saving a refit would bring. The measurement that follows fires the refit when that estimated saving over the next window exceeds the refit’s price, on both jumping and drifting streams. The prediction is that it keeps the corner start’s advantage on jumps, since it fires only for chances worth the price, and matches one full selection on drifts within a few refits. The cost to watch is the estimate’s own searches. A window’s worth of estimates is four searches of the sample, and if they are paid every window the watching could cost more than the corner start saved by not fitting.