A placement after the traffic moved

Where the landmarks stand turned a weak straight-line estimate — an estimate borrowed from an easier problem — into a strong one with four tables of exact distances, each from a chosen cell. A search guided by the tables expands a fraction of the cells. Which cells hold the tables matters a great deal: the map’s four corners beat four cells near the centre by more than three to one.

What the queries know that the map does not asked whether a system’s own query log could choose better. It chose greedily, adding whichever candidate cell most reduced the cells a sample of past queries expanded. On uniform traffic the log converged on the corners and never beat them. When every query headed for one destination, twenty queries were enough to beat the corners by 29%.

It ended on the question a real system would ask next. A placement fitted to one destination is worth something at that destination, and traffic moves. How much is the placement worth after it has moved, and when should the system choose again?

The placement being moved #

The selection moves two landmarks off the corners and towards the destination. That is what a landmark near a destination is for. The estimate of the distance to the goal is strongest when some landmark lies behind the goal, as seen from where the search starts, and a landmark next to the goal is behind it from almost everywhere.

The plates below use eight such maps with a different destination each, and a fitted placement for each. On its own destination, averaged over the eight, the fitted placement expands 73.1 cells a query where the corners expand 109.9: two thirds.

How quickly the advantage goes #

Move the destination, keep the landmarks, and run fresh queries to the new destination with both placements.

The advantage halves in about five cells and is gone at ten. A fifth of the map’s width is enough to make the fitted placement exactly as good as the corners, averaged over directions. At that distance it is worse than the corners in half the cases, because a landmark that stood behind the old destination may stand in front of the new one. Past ten cells the fitted placement is worse on average, and at thirty cells it expands nearly twice the corners’ cells.

That is steeper than the fitting suggested. The selection chose landmarks that make the estimate to one particular cell sharp, and sharpness at one cell is bought by leaving the rest of the map to the two landmarks the selection did not move. The corners are a hedge: they are never the best placement for any one destination and never far from the best for any.

What choosing again costs #

A system whose destination has moved can choose again, from the queries it has seen since. The previous essay measured what a greedy selection costs to run, and the same cost is the one that decides everything here.

A selection expands about 317,000 cells, which is the work of answering some 2,900 queries with the corners. It is the trade the rule that pays on a long enough text measured for string matchers — a preparation repaid only if enough work follows it — except that here the preparation has to be paid for again whenever the traffic moves. At the destination it was fitted to, it saves 36.8 cells a query over the corners, so it needs 8,630 queries at that destination to pay for itself. The decay plate says how long that is likely to take. The saving halves when the destination has moved five cells, so a selection is repaid only if the destination stays within a few cells for something like ten thousand queries.

The cost is almost all in trying candidates. Each of four rounds tries every remaining candidate against every one of the twenty sample queries: about 1,900 searches, at about 170 cells each. The tables themselves are not charged here, and neither is their memory, the second axis measuring what an algorithm keeps argued a structure should be priced on. A table is a full search from a candidate cell, and the twenty-five candidates’ tables are computed once and kept, so only the first selection on a map would pay for them. Charging them would make every selection dearer by the same amount and would not change the ranking below.

Four policies on streams that drift #

The destination now drifts. Before each query it steps to a random neighbouring cell with a stated probability, so over 30,000 queries it wanders a distance that grows with that probability. Four policies share the same queries.

• The corners, never fitted and never charged anything.
• Fitted once, kept: fitted to the first twenty queries, never refitted.
• Refitted every 10,000 queries, to the twenty most recent.
• Refitted on a counter: after each fit it measures the mean cells of the next 2,000 queries, then refits whenever the mean of the last 2,000 exceeds that baseline by half.

Every policy is charged the cells its queries expand and the cells each of its selections expands.

At no drift rate does a policy that chooses again come out cheapest. Up to a drift of 0.01, which takes the destination about ten cells over the stream, fitting once and keeping the result is the cheapest policy: 83.1 cells a query with no drift and 108.5 at 0.01, against the corners’ 120.3 and 143.9. At 0.03 the destination wanders more than twenty cells and the one fit is far out of place. It then costs 195.6 against the corners’ 153.2, and the corners are cheapest. The periodic policy and the counter lie between the two at every rate, except that with no drift the counter matches the one fit.

Why one fit survives so much drift is worth a sentence, because the decay plate seems to say it should not. At a drift of 0.01 the destination ends about ten cells from where it started, which is exactly where the decay plate puts the fitted placement level with the corners. But it gets there gradually. For most of the stream it is a few cells away, where the fit is still clearly ahead, and the average over the stream is dominated by those queries. A random walk covers distance slowly: in two dimensions a displacement of $d$ cells takes on the order of $d^2$ steps. So at 0.01 steps a query, five cells of drift takes a couple of thousand queries, and ten cells ten thousand.

The periodic policy is the worst of the four at every drift rate but the last, and for a plain reason. It pays for three selections a stream whether or not anything has changed, about ten cells a query each. Its queries are not even cheaper than the one fit’s at 0.01 — 107.7 against 98.7 — because a refit to the twenty most recent queries of a moving destination fits a place the destination is about to leave.

With no drift at all the counter never fires. Its baseline after the first fit is the stream’s own level, nothing raises it, and the counter costs exactly what fitting once costs. That is the one row where it is as good as the best.

Where the counter’s cost goes #

The counter does what it was built to do. It notices that its queries have become dearer and it restores them. It pays for that at a price the stream cannot repay.

The counter’s queries are the cheapest of the four, 97.2 cells a query against the one fit’s 98.7. Its refits did keep the landmarks near the traffic. But each refit costs about 10 cells a query spread over a 30,000-query stream, and the counter made more than two of them on average. What the refits recovered on the queries, one and a half cells a query, is a sixth of what one refit costs.

The arithmetic is the price plate’s arithmetic in another form. A refit costs as much as 8,630 queries at the full saving, and the saving it restores is partial and decays within a few cells. For a refit to pay, the destination must move far enough to spoil the old fit and then stay put long enough to repay the new one. On these streams it does neither for long.

One stream, drawn #

This is the stream that shows the counter at its worst, and it is worth seeing why. The destination wanders away and partly back. Each time it wanders, the counter’s rolling mean rises past its threshold, and it refits to the twenty most recent queries. Twenty queries is a small sample, and some of those refits are fitted to where the destination happened to be for a few hundred queries. Four refits after the first fit left it 55 cells a query dearer over the whole stream than the one fit kept. The one fit kept was never updated, and it is close enough to wherever the destination wanders here to beat the corners over the stream as a whole.

The refits are not bad because their samples are bad. Twenty queries was the sample the earlier essay found enough to beat the corners at a fixed destination. At a drift of 0.01 the destination moves once every hundred queries or so, so the twenty most recent queries almost always share one destination, and each refit is a good fit to where the traffic was. The trouble is only that the traffic does not stay there. A refit is a bet on the destination’s future, placed with evidence about its present.

The counter needs no model of how the traffic drifts, which was the reason for proposing it. What it lacks is a model of what it costs to act. A rise in cost of a half says that the landmarks are no longer where the traffic is. It says nothing about whether the new traffic will stay put long enough to repay 317,000 cells.

What the rule needs to know #

The measurements point to the rule a system actually needs, and it is not a better detector. It is a price. A refit should happen when the saving it is expected to recover, summed over the queries until the next refit, exceeds what it costs. Both halves are measurable from the log a system already keeps. The saving is the gap between the current mean and the mean just after the last fit. The horizon is how long the destination has stayed put in the past, which a system can read from the same log.

Against a price of 317,000 cells, that rule would refit rarely on these streams, if at all. The decay plate puts the useful life of a fit at a few cells of movement. At a drift of 0.01 a few cells take a couple of thousand queries, well short of the 8,630 a refit needs. At 0.001 they take tens of thousands, but on those streams the destination never moved far enough to spoil the first fit, so there was nothing for a refit to recover.

The numbers make the rule concrete. A fresh fit saves about 37 cells a query at its own destination, and the saving halves once the destination has moved five cells. At a drift of 0.03 steps a query, five cells of random walk take roughly 25 steps, about 800 queries. A refit therefore recovers something like 37 cells over 800 queries before its advantage halves, around 30,000 cells, against a price of 317,000. It cannot pay, however well it is timed. At 0.001 steps a query the same five cells take about 25,000 queries, and a refit made at the right moment would recover several times its price. At that rate, though, the first fit is still good by the end of a 30,000-query stream, and there is nothing to refit for.

Between those rates is a band where a well-timed refit could pay, and the counter is not a way of finding it. It measures whether the current landmarks have got worse. The rule needs to know whether new ones would stay good for long enough, and that is a question about the traffic’s future, answerable only from how the traffic has moved in the past.

That also points to the other lever, the price itself. The selection tries twenty-five candidates against twenty queries four times over. A selection that tried only the candidates near the new destination, or reused the three landmarks that are still useful and re-chose one, would cost a fraction of that. Everything on the policy plate would then move. The finding here is not that refitting is wrong. It is that at this selection’s price, on this traffic, refitting does not pay, and the counter cannot tell.

The same trade, one layer down #

A potential mended where it broke met the same shape of problem in a different structure. A stored reweighting on a graph with negative arcs is a preparation that makes every later query cheaper, and updates to the graph spoil it. How long a reweighting stays true priced the rebuild. There the cure was not to rebuild but to mend: relax only the arcs that broke and propagate from them, at a small fraction of a rebuild. That turned a stored potential from something that stopped paying once half a per cent of arcs changed into one that stayed at about two thirds of the per-query cost at every rate of change measured.

The landmark selection has no mend yet. Every refit on this page starts from nothing: it forgets the four landmarks it had, including the two corners it kept, and re-derives them at full price. That is the equivalent of rebuilding the reweighting from the virtual source every time one arc fell. The earlier essay’s lesson was that the price of a repair is a design choice, and a preparation whose repair costs as much as its construction is one whose maintenance question has already been answered.

The limits of the measurement #

One kind of drift. The destination takes a random walk. A destination that jumps — a new popular place replacing an old one — spoils a fit at once and then stays put, which is exactly the case where a refit pays. The counter would catch the jump within 2,000 queries. Nothing here measures it.

One destination at a time. Real traffic has several, with weights that shift. The previous essay found that a handful of destinations still lets a fitted placement beat the corners, and a drifting mixture is the natural extension.

The selection’s own choices. Twenty sample queries, twenty-five candidates, four landmarks, and a threshold of a half on a window of 2,000. Each is a constant somebody chose, in the sense of the threshold somebody chose. The threshold and the window decide how often the counter fires, and the sample size decides how good each refit is, and none of them was swept here.

Cells, not time. The unit throughout is cells expanded, which the cells are not the cost warned is not the same as time.

Checked answers. On the decay plate every search’s result is checked against the exact distance. The stream plates run the same search without the check, which is admissible whatever the placement, so a wrong landmark table would change the cells expanded and not the answers.

Still open: a refit that re-chooses one landmark #

The selection is expensive because it starts from nothing. After a drift, some of the old landmarks are still useful — the corners the selection kept are useful to every destination — and only the ones that were moved towards the old destination have gone stale.

The measurement that follows gives the counter a cheaper action. When it fires, it keeps three of the four landmarks and re-chooses only the one whose removal costs the recent queries least, trying each candidate against the recent sample once. That is a twelfth of a full selection’s searches. It measures the same four policies with this incremental refit alongside, on the same drifting streams and on a stream whose destination jumps. The prediction is that an incremental refit pays at drifts where a full one does not, because its price falls below the saving it recovers within a few thousand queries. On the jumping stream a counter with an incremental refit should beat fitting once. What the drifting streams will show is less certain, and it is the part worth measuring.