The candidates near where the queries end

A refit that changes one landmark kept a landmark placement up to date as the traffic on a map moved. The search is A*, which the function the caller supplies introduced as Dijkstra’s algorithm with an estimate added to each key, and here the estimate is a lower bound on the distance to the destination read off four landmarks’ tables — the device where the landmarks stand measured against the straight-line estimate on rough terrain. A placement after the traffic moved found that such a placement goes stale within ten cells of the destination it was fitted to. A placement fitted to where the queries were going beat the four corners, and went stale when the destination moved. Choosing all four landmarks again cost hundreds of thousands of cells of search. Keeping three and re-choosing the fourth cost a fifth of that. With the cheaper refit fired by a counter, a stream whose destination jumped once in 10,000 queries was served more cheaply than by any other policy measured.

The refit spent most of its searches on the replacement: 22 of its 26 trial runs tried a candidate from the 25-point lattice as the new fourth landmark. The page’s closing section argued that most of those candidates could not win. The landmark being dropped was useful to the old destination, and its replacement must be useful to the new one, so it should be one of the candidates nearest where the recent queries end. The section proposed trying only the four to eight lattice points around the destination. It predicted that the price would fall from a fifth of a full selection towards a twelfth, that the refit would lose little, and that the cheaper refit would let the counter follow jumps a few thousand queries apart.

The first two predictions hold almost exactly. The third does not, and the reason it does not is the most useful thing on the page.

Price against what the placement is worth #

The maps are the earlier pages’: four weighted 50 × 50 mazes, with 25 candidate landmarks on a 5 × 5 lattice of the nearest open cells. On each map a destination is chosen and a placement fitted to twenty queries ending there. Then, six times in turn, the destination moves to a new random cell and the placement is refitted to twenty queries ending at the new one. That gives 24 refits. Every refit drops the landmark whose removal costs the sample least, exactly as before. The unrestricted refit then tries every other candidate as the replacement. The restricted one tries only the $k$ candidates nearest the new destination, plus the dropped landmark, so that a refit that finds nothing better can keep what it had. Each is charged every cell its trial searches expand. Each placement is then measured on forty fresh queries to the new destination.

Trying only the four nearest candidates costs 0.085 of a full selection, against 0.236 for trying all of them, and its placements serve fresh queries within 2.6% as well. The earlier page guessed a twelfth for the full incremental refit and found a fifth. The twelfth turns out to be the price of the restricted one: 0.085 is one part in 11.8.

The quality curve is flat almost immediately. Two candidates are too few: they miss the best replacement often enough that fresh queries cost 14% more. From four candidates on, the restricted refit chooses the same placement as the unrestricted one in 19 of 24 refits. Its fresh-query cost is within 3% at four and within half a percent at twelve. Six and eight buy nothing that four does not.

Four is the natural number for the lattice, not a tuned one. The candidates are a 5 × 5 lattice on a 50 × 50 map, a point about every twelve cells, so a destination lies inside a square of four lattice points and up to six cells from the nearest of them. Those four surround it and are nearly equidistant from it, and which of them a search values most depends on the walls between. Two candidates choose among them by grid distance alone and end with a different placement from the full search in ten of the 24 refits; four take the whole square.

The prices here are measured on this experiment’s own samples. The unrestricted refit costs 0.236 of a full selection rather than the 0.19 the earlier page measured, because these refits start from placements fitted to a previous destination, not from the corners, and their trial searches are a little longer. The ratio between the restricted and unrestricted refits, 0.36, does not depend on that.

Where the winner lies #

The prediction’s reasoning was that the right replacement is near the destination. The unrestricted refit’s own choices can be ranked by how far they are from it.

The full search chooses the candidate nearest the destination in 10 of 24 refits, and one of the four nearest in 19. The reason is in the bound the landmarks give. The A* lower bound from a landmark $L$ is $|d(L, t) - d(L, v)|$. When $L$ is at the destination $t$ itself, this is $d(t, v)$, the exact remaining distance, and a search guided by an exact bound expands only the cells on a shortest path. A landmark close to the destination gives a bound close to exact for every query ending there, whatever its source. An estimate is a reweighting showed what that means for the search: A* is Dijkstra on arcs repriced by the estimate’s drop across them, and an exact estimate reprices every arc off a shortest path upwards and every arc on one to zero, so the search expands little beyond the path it returns. Three kept landmarks fitted to earlier traffic are usually far from the new destination, so the one being chosen is the only one that can supply that, and the nearest candidates are the ones that supply it best.

The other five winners lie far off — ninth to twentieth by distance — and they are not the same kind of refit. In those five the refit was barely worth making. The stale placement already served fresh queries within 12% of what the refitted one does, because a kept landmark happened to lie near the new destination already. The full search, finding no large improvement anywhere, picked whichever distant candidate shaved the sample’s cost a little. The restricted refit, trying only the nearest four, gets 11% less than it in those five refits, and about what not refitting at all would get. In the other nineteen, where the refit halves the cost of a fresh query, the restricted refit gets exactly what the full one does.

So the restriction loses only where the refit had nothing to find. That is as good a form of loss as a cheap search can have. It is the same finding where the landmarks stand made for placements in general: a landmark’s value is concentrated behind the destination as the query sees it, and a candidate far from every destination in the traffic is worth little to it.

One refit on its map #

The picture shows why the nearest candidates are the right ones to try, and why the dropped landmark is the one it is. The three kept landmarks sit on the map’s edges — at the top, at the middle of the right edge and high on the left — where each bounds many destinations reasonably. The dropped one sat inside the map at (12, 25), placed for the previous destination and useful to nothing the new traffic needs. The winner is the lattice point just below the new destination, at the map’s bottom edge, which gives queries from anywhere above it a bound close to exact.

A search that tries every candidate spends most of its effort on points like the ones across the map, each of them a full run of the twenty-query sample. The restricted search tries the four points of the lattice that surround the destination, and the dropped landmark to keep as a fallback. It needs no knowledge of the map beyond the lattice coordinates and the destinations of the recent queries, which the sample already holds.

A cheaper refit on destinations that jump #

The earlier page’s best result was on streams whose destination jumps to a random cell at random times. There a counter fired the incremental refit whenever the mean cost of the last 2,000 queries rose by half over its level after the previous refit. At one jump in 10,000 queries that beat every other policy, and at one in 2,500 it lost to the corners. The closing section’s argument was that the refit’s price was holding it back, and that a refit a third as expensive could afford a counter that watched a shorter window and fired sooner.

Where jumps are rare, the cheaper refit wins by a wide margin: 80.9 cells a query at one jump in 10,000, against 94.1 for the unrestricted refit and 124.9 for the corners. At one jump in 5,000 it is 107.8, against 114.2 and 127.2. Where jumps come every 2,500 queries, it still loses to the corners, 138.6 against 126.8, and at one in 1,000 it loses by 16%.

The prediction assumed the refit’s price was what held the counter back at frequent jumps. The accounting says otherwise. A refit restricted to four candidates costs about 32,000 cells; a stream of 30,000 queries at 125 cells a query spends 3.75 million. Refitting five times costs less than a twentieth of the stream. The preparation charge on every policy that refits is dominated by something else: the one full selection at the start of the stream, which every policy but the corners makes once. A full selection costs about 380,000 cells on these maps — 12.6 cells a query over a stream of 30,000, a tenth of the whole bill, before a single refit. It is preparation repaid over the queries that use it, the trade how long a reweighting stays true priced for Johnson’s one Bellman–Ford: worth making when many queries share it, and not when the thing it was fitted to changes before they arrive.

The window, and what it cannot fix #

A shorter window helps where jumps are rare: 80.9 at a window of 250 against 89.9 at 2,000, because the counter notices a jump sooner and the queries between the jump and the refit, all served by a stale placement, are fewer. It is not free. A window of 250 queries averages a quarter as many searches as one of 2,000, so its mean is twice as noisy, and a counter comparing a noisy mean with a threshold fires on noise as well as on jumps. At one jump in 10,000 the short window fired 2.0 times a stream on average, the same as the long one: the noise was not enough to trigger a refit here, because a stale placement after a real jump costs twice what a fitted one does, and that difference is far larger than the noise in 250 searches. Where jumps come every 2,500 queries, no window gets the counter under the corners.

The reason is the arithmetic the earlier page set out for its own break-even, and the cheaper refit does not change it. Between a jump and the refit that answers it, every query is served by a placement fitted to a destination that no longer exists. That placement is much worse than the corners, which serve every destination tolerably: what the queries know that the map does not measured a fitted placement losing its advantage within a few dozen cells of its destination. A window of 250 queries notices a jump after a few hundred queries at best, and often later, since one noisy window can hide it. After the refit the new placement has to serve enough queries to repay the excess of that stale stretch. At one jump in 2,500, detection and payback use up most of the interval before the next jump, and a fitted placement’s advantage is never collected for long.

Over the whole stream the counter fires far less often than the destination jumps: about five refits to thirty jumps at one in 1,000, and four or five to thirteen at one in 2,500. Many jumps land where the stale placement is not much worse than average, and the counter, rightly, does not fire. The ones it does answer, it answers late. A cheaper refit makes each answer cheaper and does nothing about lateness.

What was measured and what was not #

Four maps and 24 refits. The price and quality figures are over 24 refits on four maps, with twenty-query samples and forty fresh queries each. The ranks of the full search’s winners, 19 of 24 within the nearest four, are a count, not a rate; the ranks beyond four came from refits that barely improved on the stale placement, and a larger sample could find a refit where a distant winner matters.

Sources spread over the whole map. Every query starts at a uniformly random open cell. A landmark near the destination serves such traffic from every direction, which is why nearness to the destination alone ranks the candidates well. Traffic whose sources cluster — every query from one district to another — would also value a landmark behind the sources, and a restriction to candidates near the destination would miss it. The full search’s far winners were few here partly because no source was ever special.

Lattice distance, not path distance. The nearest candidates are ranked by grid distance from the destination, which is free to compute. In a maze the path distance can be much longer than the grid distance, and a candidate on the far side of a wall from the destination is nearer on the grid than it is useful. Ranking by path distance needs the destination’s own table, which is the search the restriction exists to avoid, unless a landmark already sits near the destination.

One threshold. The counter fires at a 50% rise over its level after the last refit, as on the earlier page — a constant of the kind a potential mended where it broke had to choose for a stored reweighting, where rebuilding at every break stopped paying once breaks came often. A lower threshold would fire sooner and more often, and at frequent jumps that is the direction that might help; it was not swept.

The first selection. Every policy but the corners begins with a full selection, charged at about 380,000 cells. A policy that began from the corners and made only restricted refits would never pay it, and on streams that jump often that could be most of the difference between the counter and the corners.

Still open: starting from the corners and never selecting in full #

The accounting above found that once the refit is cheap, the largest single preparation cost on a jumping stream is the full selection at the start, which fits all four landmarks to the first destination. The corners need no preparation at all and are never far from good. A policy could start from them and use only restricted refits, so its first refit would replace one corner with a candidate near the first destination, and every later refit would replace whichever landmark the new traffic values least.

The measurement that follows runs that policy on the same jumping streams. It starts at the corners, fires the four-nearest refit on the counter at a window of 250, and never makes a full selection. It compares that policy with the counter here and with the corners alone. The prediction is that it closes most of the gap at one jump in 2,500, since it saves the 12.6 cells a query the first selection costs. At that rate the counter here loses by 11.8. If it does, the counter’s failure at frequent jumps was a matter of where it started, not how late it was. If it does not, lateness is the whole of the problem, and the next thing to try is a placement that keeps one landmark free to follow the traffic while three stay at the corners for good.