A refit priced before it is made

Starting from the corners kept a set of four landmarks for shortest-path searches on a weighted maze and changed them as the traffic moved. Its placement started at the maze’s four corners, which need no preparation and are never far from good. A refit that changes one landmark supplied the refit: re-choose one landmark from the four candidates nearest where the queries end. The refit was fired by a counter that watched the mean cost of recent queries and fired when it rose by half. On traffic whose destination jumps at random times, that closed 82% of the gap between the counter that starts with a full selection and the corners, at one jump in 2,500 queries.

On drifting traffic, where the destination walks one step at a time, the counter never fired. From the corners, concentrated traffic raises no cost, because the corners serve every destination about equally badly. The chance the counter missed was not cost that rose but cost that could fall. The essay’s closing section proposed a detector built on a comparison rather than a threshold. Every window of queries, price the current placement on a small sample of recent queries against the best of the four candidates nearest their destination, and fire the refit when the estimated saving over the next window exceeds the refit’s price. It predicted that this keeps the corner start’s advantage on jumps and matches one full selection on drifts within a few refits. It named the cost to watch: the estimate’s own searches, paid every window whether they find anything or not.

Pricing a refit before making it #

The watching policy starts at the corners, as the corner start does, and makes no full selection. Every window — 250, 500, 1,000 or 2,000 queries — it takes the last twenty queries served. Their cost under the current placement is already known, since they were charged when they were answered, so that side of the comparison is free. It then tries each of the four candidates nearest those queries’ destinations in place of the current landmark farthest from them, running each variant on the twenty queries. Each of those four searches of the sample is charged as preparation. The best variant’s saving, scaled from twenty queries to the next window, is the estimate. If it exceeds the price of the last refit made, or nine sample searches before any refit, the refit fires, and the refit itself is the corner start’s, charged as before.

Two things are deliberately cheap about the estimate. It never searches for which landmark to drop; it drops the one farthest from where the traffic ends, which needs only coordinates. And it prices four candidates, not every candidate the full refit would try. Both are guesses that the refit, when it runs, may overrule. The estimate only has to say whether a refit is worth trying.

Everything else is the earlier pages’: four maps of 2,500 cells with weighted edges, 30,000 queries a stream, every search’s expanded cells charged. The watching policy is run beside the corners, one full selection kept for the whole stream, the counter that starts with a full selection, and the corner start’s counter, each counter policy shown at its best window.

On traffic that jumps #

At one jump in 2,500 queries the watching corner start costs 120.5 cells a query against 128.9 for the corner start’s counter, 138.6 for the counter that starts with a full selection, and 126.8 for the corners. It is the first policy measured in this strand to beat the corners at that jump rate. At one jump in 5,000 it costs 98.1 against the counter’s 102.2, and at one in 10,000 it costs 80.2, level with the full-selection counter’s 80.9 and below the corner start’s 85.1. The prediction said the watch would keep the corner start’s advantage on jumps. It does better than keep it, at every jump rate but the fastest.

At one jump in 1,000 it is the dearest of the policies that start at or stay at the corners: 154.1 against the counter’s 145.1 and the corners’ 142.7. When the destination moves every thousand queries, a placement fitted to it is stale by the time it has paid for itself. The watch sees a saving on nearly every window, fires 8.3 refits a stream, and each one serves a destination that is gone within a thousand queries. The corner start’s counter, which fires only when cost has risen by half, makes two. At that rate the counter’s insensitivity is its virtue: it declines chances that are real but too short-lived to collect.

What watching costs #

Watching every 250 queries spends 42.0 cells a query on estimates alone, a third of what the queries themselves cost; watching every 2,000 spends 4.5. Four searches of a twenty-query sample cost about as much as eighty queries, and paid every 250 queries that is a third of the traffic again. The section predicted exactly this risk: if the estimates are paid every window, the watching could cost more than the corner start saved by not fitting. At 250 it does, 168.0 cells a query against the corners’ 126.8. The cost falls in proportion to the window, and at 2,000 queries the estimates are 4% of the bill.

A longer window also makes refits later, since a chance that opens just after a check waits up to a window to be seen. At one jump in 2,500 that lateness is cheaper than the watching it saves. Every 2,000 queries the watch fires 4.0 refits a stream and spends 4.0 cells a query on them, against 5.0 refits and 6.1 cells every 1,000. The best window moves with the jump rate — 1,000 queries at one jump in 1,000 and in 5,000, 2,000 at one in 2,500 and in 10,000 — and at no rate is it shorter than a thousand. A placement after the traffic moved found a fitted placement’s advantage gone once the destination had moved ten cells, and reversed at thirty. The watch’s window has to be short enough to catch that decay and long enough that looking does not cost more than what it finds.

Why starting at the corners makes watching cheap #

The watch compares two numbers, and the comparison is only as good as its baseline. The baseline is the current placement’s cost on the last twenty queries, and from the corners that cost moves little with the destination. Where the landmarks stand found the corners a placement that is never far from good for any query, and the earlier page measured how little their cost varies: blocks of 500 queries varying with a standard deviation of 39 to 64 cells around a mean near 125, where a fitted placement varied by 77 to 150 around 200. A candidate that beats the corners on twenty queries to one destination is therefore beating a steady number, and the saving the estimate reports is mostly the candidate’s doing, not the sample’s luck.

After the first refit that stops being true. The placement now has a landmark fitted to one destination, and its cost on the next twenty queries depends on whether they still go there. The estimate compares a volatile baseline with candidates that are volatile the same way, and its saving is noisier. That is part of why the watch refits more often than it should on fast jumps: some of its estimated savings are a sample of twenty queries that happened to favour a candidate. What the queries know that the map does not found twenty observed queries enough to fit a placement well when they share a destination, and the watch leans on that. It also inherits the other half of the finding, that twenty queries are a thin description of traffic that is about to change.

The price the estimate charges itself #

Each window’s estimate costs four searches of twenty queries, about eighty queries’ worth of cells, whether it finds anything or not. A refit, when it fires, costs about nine such searches. So a window of 2,000 queries spends about 4% of its traffic’s cost on looking, and a refit that fires once in four windows spends about as much again. An estimate is a reweighting showed that a landmark placement is a reweighting of the graph, paid for once and used by every search after it. The watch adds a small recurring charge to that one-off payment, the price of knowing whether the reweighting is still the right one. At each jump rate’s best window it runs from 2.9 cells a query, at one jump in 10,000, to 11.4, at one in 1,000, and at a window of 250 queries it is over forty, which is why the window matters more than any other setting of the policy.

On traffic that drifts #

On drifting traffic the watch costs 107.4 cells a query at a step every thousand queries, against 103.3 for one full selection kept all stream and 132.8 for the corner start’s counter. At a step every hundred queries it costs 108.6 against 108.5. On the fastest drift, a step every thirty-three queries, the full selection kept all stream falls behind at 195.6, because the destination walks away from where it was fitted. The watch holds at 123.2. The prediction said the watch would match one full selection within a few refits, and it comes within 4% on the slow drifts and 5% at a step every three hundred, having made 1.8 to 3.5 refits a stream and no full selection at all.

The corner start’s counter makes about one refit a stream on these streams. That is the whole failure the section set out to repair. Its counter measures a rise, and from the corners a drifting destination produces none. The watch measures a difference between what the placement costs and what a nearby alternative would, which the corners produce all the time on concentrated traffic.

One stream where the watch goes quiet #

The averages hide one way the watch fails, and a single stream shows it. On this map, with the destination stepping once every three hundred queries on average, the watch refits twice early and serves the middle of the stream at about 72 cells a query, half the corners’ cost. Then the destination drifts on and the watch’s cost climbs, to 204 cells a query by 21,500 and 263 by 27,500, above the corners’ 224. It does not refit again. Over the stream it costs 149.8, level with the corners.

The likely reason, argued from how the estimate is built rather than traced landmark by landmark, is how cheap it was made. It prices each candidate in place of the landmark farthest from the traffic’s destination, and by late in the stream the landmark it would be right to drop is not the farthest one. The two refitted landmarks sit near where the destination used to be, which is not far from where it is now, and the landmark that is useless is one of those. So the estimate tries the right candidates against the wrong landmark, finds no saving worth the price, and stays silent while its placement ages. The full refit, if it ran, would search for which landmark to drop and find it. The estimate saved that search, and on this stream the saving was the failure.

What the estimate buys, and what it costs to make it honest #

The watch refits two to four times as often as the corner start’s counter, and it is cheaper wherever those refits find a destination that stays. On jumps every 2,500 to 10,000 queries and on every drift, that is true, and the refits pay. On jumps every 1,000 queries they do not, because the destination they were fitted to has moved on before they are repaid. The counter and the watch are two answers to one question — should the placement change now? — and they fail in opposite directions. The counter waits for evidence that the placement has become bad, and misses chances where it was never good. The watch looks for evidence that a better placement exists, and takes chances too short-lived to repay it.

How long a reweighting stays true found a stored potential repaying itself within three queries on a graph that held still and worth nothing once half a per cent of its arcs were redrawn between queries: preparation pays only while what it was fitted to lasts. The watch’s estimate has the same horizon built into it: it scales a twenty-query saving to the next window, which is a bet that the next window looks like the last twenty queries. On jumps every thousand queries that bet loses. A version that scaled the saving to the expected time until the destination moves — which the stream’s own jump history estimates — would bet more modestly on fast traffic. That version was not built.

What was not measured #

One estimate, cheapened twice. The estimate drops the landmark farthest from the destinations and prices four candidates. An estimate that searched for the landmark to drop, as the refit does, would cost about twice as much a window and would not go blind on the stream shown above. Whether that is worth it at a window of 2,000 queries, where watching costs 4.5 cells a query, was not measured.

The price of a refit is the last refit’s cost. Before the first refit it is nine sample searches. A refit’s real cost varies with how many candidates it tries and how dear the sample is, and pricing it from the last one is a guess that is sometimes stale.

Four maps, one stream shape each. As on the earlier pages. The jump rates and drift rates are the earlier pages’, so the watch is compared with them on identical streams.

Fixed windows. Each stream is watched at one window for its whole length, and the best of four windows is reported. A watch that shortened its window when its estimates kept finding savings, and lengthened it when they kept finding none, would choose the window from the traffic. It was not built, and the plates suggest the best window changes by no more than a factor of two across every stream measured.

Twenty queries a sample. The sample size is the refit’s own, and it was not varied. A larger sample would make the estimate less noisy and dearer in proportion.

Still open: a watch that knows how long a chance will last #

The watch lost where chances were short: jumps every thousand queries, where it refitted eight times a stream for destinations that were gone before the refits paid. Its estimate assumes the next window will look like the last twenty queries, and on fast traffic that is false. The stream itself holds the evidence of how false. Each refit the watch makes is followed by some number of queries before the next one fires, and those intervals are a measurement of how long a fitted destination lasts.

The measurement that follows gives the watch a horizon: the saving is scaled not to the next window but to the mean interval between its own recent refits, capped at the window. On slow traffic, where refits are rare, the horizon is long and nothing changes. On fast traffic the horizon shortens, the estimated saving shrinks, and the watch should fire less. The prediction is that it recovers the corner start’s cost at one jump in 1,000, about 145 cells a query, and keeps its gains at one in 2,500 and slower. It could fail at the transition. There the horizon learned from one burst of fast jumps would suppress refits just as the traffic settles, and the watch would have learned to be as blind as the counter it replaced, for the opposite reason.