A horizon the stream can supply

A refit priced before it is made gave a landmark search a watch. The placement starts at the four corners of a weighted maze, and every window of queries the watch takes the last twenty queries served and tries each of four candidate landmarks near their destinations in place of the current landmark farthest from them. It scales the best candidate’s saving on those twenty queries up to the next window, and refits when that estimate exceeds the price of the last refit. It beat the corners wherever the destination jumped every 2,500 queries or less often, and on every drifting stream. Where the destination jumped every thousand queries it lost: 154.1 cells a query against the corners’ 142.7. It refitted eight times a stream for destinations that were gone before the refit had paid.

Its closing section located the fault in the estimate. Scaling a saving to the next window is a bet that the next window will look like the last twenty queries, and on fast traffic the bet loses. The section proposed a horizon: scale the saving not to the window but to the mean interval between the watch’s own recent refits, capped at the window. On slow traffic the horizon would be long and nothing would change; on fast traffic it would shorten, the estimate would shrink, and the watch would fire less. The prediction was that this recovers the corners’ cost at one jump in 1,000, about 145 cells a query, and keeps the gains at one in 2,500 and slower. The risk named was the transition, where a horizon learned in a burst of fast jumps might suppress refits just as the traffic settles.

The watch, and four horizons for it #

Everything is the earlier page’s: four maps of 2,500 cells with weighted edges, the one-landmark refit of a refit that changes one landmark, 30,000 queries a stream, every search’s expanded cells charged, the estimate’s four candidate searches charged as preparation, the refit charged when it fires. Destinations jump at random times, on average every 1,000 to 10,000 queries, or drift a step to a neighbouring cell with a chance of 0.001 to 0.03 before each query. Each policy is shown at the better of two windows, 1,000 and 2,000 queries, the two the earlier page found best at every rate.

The only change is the number the estimated saving is scaled to. The window, as before. Its own refit intervals, the proposal: the mean of the last three intervals between the watch’s refits, capped at the window. Any change of destination: the mean of the last five spells during which every query went to the same cell. Moves beyond ten cells: the mean of the last five stretches of traffic during which every destination stayed within ten cells of where the stretch began. Ten cells is the distance at which a placement after the traffic moved found a fitted placement’s advantage over the corners gone. The true future: the number of queries until the destination next lies more than ten cells from the current one, read off the stream ahead. No policy can know this, and it is measured to bound what any horizon could do.

A horizon that is always the window #

The proposal changes nothing, and the reason is arithmetic rather than measurement: the watch looks once a window, so two of its refits can never be less than a window apart, and a horizon capped at the window is the window. Across every jump stream and map at a window of 2,000 queries the watch made 60 intervals between refits, the shortest exactly 2,000 queries and 34 of them exactly one window. The horizon computed from them took the value 2,000 at every check, and the policy with it costs what the watch costs, to the cell, on every stream.

The intervals do carry information. At one jump in 1,000 they cluster at one window, and at one in 10,000 they spread over several. But what they measure is how often the watch found a saving worth taking, and the watch’s own check period sets their floor. A measurement cannot report a duration shorter than the interval at which it is taken. The destination may move every few hundred queries, and a watch that looks every two thousand will see refit intervals of two thousand.

So the horizon has to come from something that is observed more often than the watch looks. The stream supplies it: every query that is served names its destination, and the watch can see every one.

Two horizons from the traffic #

A horizon from any change of destination falls to 98 queries on a stream that steps once in a hundred queries, and the watch stops refitting: it costs 148.7 cells a query, more than the corners’ 143.9, where the watch without a horizon costs 108.6. On a drifting stream the destination changes constantly and moves hardly at all. After a hundred steps it is typically about ten cells from where it started, and a placement fitted to it keeps most of its value that whole time. A horizon that counts every change as the end of a chance tells the watch that no saving lasts more than a hundred queries. No refit at nine searches’ price can pay back over a hundred queries, so the watch never fires. At a step every 33 queries its horizon is 39 queries and it costs 158.9.

A horizon from moves beyond ten cells stays at the window on every drift, and costs what the watch costs, to within half a cell. At a step every thousand, every three hundred and every hundred queries it is the watch to the cell; at a step every 33 queries its horizon is 1,962 queries, the stretches occasionally ending inside a window, and it costs 123.7 against 123.2. The ten-cell rule counts distance, not change, and a drifting destination rarely travels ten cells within a window. On jumps the two horizons agree, since a jump moves the destination far away at once and every jump ends a stretch under either rule.

The difference between the two is the point a placement after the traffic moved made. What makes a fitted placement stale is not that the destination changed. It is how far it went. A horizon for a landmark placement has to be measured in the same units as the placement’s decay, and a count of changes is not one.

Jumps: a gain where the watch already won #

Scaled to moves beyond ten cells, the watch costs 116.4 cells a query at one jump in 2,500, against 120.5 without a horizon, and at one in 5,000 and 10,000 exactly what it cost before. The horizon at one in 2,500 averages 1,540 queries against a window of 2,000. It shrinks some estimates by a quarter, the watch declines one refit a stream in four (3.0 against 4.0), and on balance the refits it declines were ones that would not have paid: its queries cost 109.0 cells against 112.0, as well as the refits saved. At one jump in 5,000 and slower the stretches are longer than the window, the horizon is capped, and nothing changes. That half of the prediction holds.

At one jump in 1,000 it costs 150.7 cells a query, against 154.1 without it and the corners’ 142.7. The horizon averages 864 queries, the estimates shrink by more than half, and the watch refits 7.8 times a stream instead of 8.3. It is less wrong and still wrong. The other half of the prediction, that a horizon recovers the corners’ cost at this pace, fails.

The true future does recover it, just: 142.9 against 142.7, at a window of 2,000 queries. A watch that knew exactly how long each destination would stay within ten cells would, at this pace, cost what the corners cost and no less. So no horizon estimated from the past can do better than tie the corners at one jump in 1,000, and the one measured here falls eight cells short of that tie.

The future is not the best horizon everywhere. At one jump in 2,500 it costs 117.3, a cell more than the horizon learned from the traffic. The ten-cell rule is a rule about when a fitted placement stops paying, not an exact one, and knowing the future of a proxy is not knowing the future of the saving. The learned horizon, averaging over five past stretches, happens to be the better proxy on these streams.

What the past can say about a memoryless stream #

The gap between the learned horizon and the future at one jump in 1,000 is not a gap in accuracy on average. The learned horizon averages 864 queries there, and the future’s own horizon averages 895. The two agree on how long a destination lasts. They disagree about which destinations will last.

The jumps in these streams come at random times, each query with the same small chance of one. A process like that has no memory. However long the destination has already stayed, the expected time until it next jumps is the same, a thousand queries on average. So the most any record of the past can tell the watch is that average, and a horizon learned from five past stretches is an estimate of a constant. Once it has that constant, it tells the watch the same thing at every check: a saving here is worth about 864 queries. Some of the destinations it then refits for leave after fifty queries and some stay for three thousand, and nothing in the stream before the check distinguishes them.

The future distinguishes them exactly. At each check it knows whether this destination is about to leave, declines the refits that would be wasted, and takes the ones that would pay for a long time. That is information no estimate from the past can hold on a stream like this. It is why the future ties the corners at one jump in a thousand and the learned horizon cannot. It is also why the learned horizon comes within a cell of the future at one jump in 2,500 and does better than it at one in 5,000. There the mean is long enough that most refits pay whichever destinations they meet, and knowing which will leave early is worth little.

Real traffic is rarely memoryless. A destination that has been popular for an hour is often more likely to stay popular for another than one that became popular a minute ago, and a horizon conditioned on the current spell’s age could use that. On these streams there is nothing of the kind to use, by construction. The candidates near where the queries end chose the refit’s candidates from the destinations the traffic had actually named. A horizon can only be chosen from what the traffic has shown so far, and a memoryless stream shows only its rate.

Where the cost goes at one jump in a thousand #

At one jump in 1,000 every watching policy’s queries are cheaper than the corners’ — 130 to 133 cells a query against 142.7 — and every one of them gives that saving back in refits and in looking. The watch without a horizon saves 10.1 cells a query on its searches and spends 10.2 on refits and 11.4 on its estimates. The ten-cell horizon saves a little more, 12.5, and spends 9.4 and 11.1. It declines half a refit a stream, and each declined refit saves its price and loses a little of what it would have bought.

The looking is the part no horizon can reach. The watch runs four sample searches every window, whether it then fires or not, and at a window of 1,000 queries that is 11 cells a query. A horizon changes only whether the watch fires after looking. An estimate is a reweighting described a landmark placement as a reweighting of the graph paid for once and used by every search after it; the watch adds a recurring charge for checking that the reweighting is still the right one, and it is that recurring charge, not the reweighting, that fast traffic makes too dear. It does not make the looking cheaper, and at this pace the looking alone costs more than the refits save. The true future ties the corners at either window, and in two different ways. At 1,000 queries it refits only for destinations that will stay, so its queries fall to 127.0 cells, and the looking, at 10.7, uses the saving up. At 2,000 it looks half as often, 5.6 cells a query, and sees half the chances, so its queries cost 132.6: 142.9 in all against 143.1. The learned horizon is dearer at the longer window than at the shorter, 151.8 against 150.7, because it cannot tell which of the chances it sees are worth taking.

So the watch’s loss at fast jumps was never mainly in its estimate. Starting from the corners found the full selection that every refitting policy made at the start to be the charge the corners never paid. Here the charge is the watch’s looking, paid every window, and at one jump in a thousand no amount of care in deciding when to refit brings it back.

Traffic that changes pace #

When jumps every thousand queries give way to one every ten thousand, the learned horizon costs 127.4 cells a query against the watch’s 126.0. That is the transition the proposal worried about, and it happens, mildly. In the fast half the horizon shortens to a few hundred queries and the watch refits 3.3 times rather than 4.0. When the pace changes, the horizon is still the mean of the last five stretches, all short, and it suppresses the first refit of the slow half: 0.8 refits in the second half against 1.0. Five stretches of memory is one or two windows at the fast pace and many windows at the slow one, so the horizon forgets fast traffic slowly. The cost is 1.1%.

The reverse is harmless. When slow traffic turns fast, the stretches shorten at once, since every jump ends one, and the horizon follows within five jumps. It costs 123.8 either way, and so does the watch. Both are well below the corners’ 132.9, because the slow half pays for everything.

The true future beats both on both streams, by 3.6 to 7.5 cells a query. How much of that could a better learned horizon recover? The switch suggests a horizon with a shorter memory, which would follow a change of pace faster and forecast worse within a steady one. How long a reweighting stays true found preparation paying only while what it was fitted to lasted. The horizon is an estimate of that duration, and it pays a stale-estimate cost of its own whenever the duration itself changes.

The limits of the measurement #

Four maps, one seed each. Every number is a mean over four maps and one stream a map, and every cost is a count of expanded cells, the unit counting on a graph chose because no comparison or swap counter sees what a search spends. The earlier pages’ differences of a few cells a query at one jump in 2,500 are of the same size as the variation between maps, and the 3.4% gain there should be read with that in mind.

Two windows. Each policy is shown at the better of 1,000 and 2,000 queries. The earlier page measured 250 and 500 as well and found them never best, so they were not re-run.

One distance. Ten cells comes from the earlier page’s measurement of where a fitted placement’s advantage vanishes on these maps, averaged over directions. A distance chosen per map, or learned from the placement’s own estimated savings, might do better. It was not tried.

Five stretches of memory. The learned horizons average the last five stretches or spells. Three and ten were not tried, and the transition result says the choice matters.

Still open: a watch that looks less when chances are short #

At one jump in a thousand the watch’s looking costs more than any refit saves, and even the future ties the corners only by spending on refits and looking exactly what its better queries save. The looking is the one charge a watch controls outright, and the horizon already tells the watch when chances are short. It can use that to decide how often to look, not only whether to fire. A watch whose learned horizon falls below half its window could double the window, and halve it again when the horizon comes back to the window. It would then spend less on looking exactly where looking finds nothing worth taking.

The measurement that follows gives the watch that rule, with windows from 1,000 to 8,000 queries, and runs it on every jump and drift rate and on the two streams that change pace. The prediction is that it ties the corners at one jump in 1,000, about 143 cells a query, by looking every four or eight thousand queries there. It should keep the 116.4 at one in 2,500 and match the watch on every drift, where the horizon stays at the window and so does the window. It could fail on the switch from fast to slow traffic. There a watch that has stretched its window to eight thousand would see the slow half’s first chance up to eight thousand queries late, and the saving the slow half pays for everything with would be the part it misses.