What the queries know that the map does not

Where the landmarks stand measured four rules for choosing the cells a landmark estimate is built from, and found that the choice is worth more than the number: four landmarks at a map’s corners expanded 126 cells a query where four near its centre expanded 423, and the standard rule — each landmark as far as possible from the ones before — lost to the corners on all eight maps.

Every one of those rules reads the map and nothing else. That is a strange thing for them to do, because the quantity deciding whether a landmark is useful is not a property of the map at all. A landmark helps a query when it lies behind the goal as seen from the source, so that the difference of two exact distances is nearly the whole route; a landmark beside the route helps nothing. Which landmarks lie behind which routes depends on where the routes run, and where the routes run is a property of the queries.

A system that has answered some queries has that property written down. This page gives a selection rule the query log and asks what it is worth.

The rule, and what it costs to run #

The rule is the obvious greedy one. Start with no landmarks. For each candidate cell, build its table of exact distances, add it to the set already chosen, and rerun the whole sample of past queries with the resulting estimate, counting the cells expanded. Keep whichever candidate lowers that total most. Repeat until four landmarks have been chosen.

The candidates are the open cells nearest an evenly spaced lattice of twenty-five points across the map, and the lattice includes both ends of each axis. Including the ends is not a detail. The rule being measured against puts its landmarks in the corners, and a candidate set that stopped short of the far edge would be a handicap dressed up as a finding.

The shape of that descent is the usual one for a greedy set: the first choice buys most, and the fourth is still buying something. Nothing here says four is the right number, and where the landmarks stand found that doubling four to eight bought less than moving four to better cells, so the interesting question was never how many.

The cost is the part worth naming early. Each round evaluates every remaining candidate by rerunning the whole sample, so the preparation runs rounds × candidates × sample searches — four times twenty-five times two hundred, which is eighteen thousand eight hundred A* searches to place four landmarks. The corner rule runs none. A selection procedure whose unit of work is the same as the unit of work it is trying to reduce is a search over searches, and the arithmetic below takes that seriously rather than reporting the placement and stopping.

There is no cheaper way to score a candidate, and that is a property of the estimate rather than an omission. The estimate is a maximum over the landmark tables, so what one landmark contributes depends on what the others already contribute: a cell whose table is excellent on its own adds nothing if a chosen landmark already bounds the same routes tightly. A score computed for a candidate in isolation would therefore be a score for a different rule. The greedy structure is the cheapest thing that respects that dependence, and it still has to run the sample once per candidate per round.

Greedy is also not optimal, and the gap is not bounded here. Choosing the four cells that together minimise the sample’s cost would mean scoring every four-subset of twenty-five candidates — 12,650 of them — at the same cost per score, which is thirteen times the preparation for a placement that is better by an unmeasured amount. Everything below is therefore a statement about the greedy rule and not about what a query log is worth in principle.

Uniform queries: two hundred observations to draw level #

The first measurement gives the rule what a query log usually looks like in these experiments — source and goal drawn uniformly from the open cells — and sweeps how many of them it sees. The landmarks it chooses are then judged on 150 fresh queries it has never seen, on each of eight maps.

The upper curve falls steadily and lands on the corner rule’s line. At one observed query the greedy choice expands 211 cells against the corners’ 126 — two thirds worse than a rule with no information at all — and it is still 12% worse at twenty. It first beats the corners on any map at fifty observations, on two maps of eight, and at two hundred it is at 125.7 against 126.3 and ahead on three maps of eight. That is not a win; it is a draw inside the spread between maps.

The lower curve is why. It is the same four tables, measured on the queries they were chosen to be good at, and at one observation it reads 43 cells against the 211 the same tables cost on queries they have not seen. A landmark chosen to make one route cheap makes that route very cheap indeed: on one map the single sample query cost 8.0 cells with the tables fitted to it and the fresh queries cost 201.9 with the same tables, a factor of twenty-five between what the sample reported and what the rule delivered.

That gap is overfitting with a number on it, and the sweep measures the gap closing rather than taking it on trust. At twenty observations it is 113.3 against 141.3 — the sample still claims a quarter more than the queries deliver. At two hundred it is 124.4 against 125.7, and at that point the sample has stopped being a small set of particular routes and started being a description of the distribution. Anyone choosing a placement from a log and reporting what it cost on the log is reading the lower line and will ship the upper one.

The mechanism is visible in the choices themselves. On one map at five observations the rule picked (10, 0), (1, 36), (49, 37) and (12, 12) — a set with one landmark in the interior and no two of them opposite. Those four cells are behind the five sample routes; they are behind an ordinary share of everything else. At two hundred observations the same map’s rule picked (0, 0), (49, 0), (49, 49) and (0, 49). Nothing in the rule changed between those two runs except how much evidence it had, and the evidence it needed was enough to stop the particular routes from mattering.

What it converges to #

The convergence is not approximate.

Given enough uniform queries, the rule picks the four corners — the same four cells, in a different order, at the same cost per query to the last tenth. Eighteen thousand eight hundred searches were spent discovering a fact about the shape of the map, and the map was available for free.

That is worth stating as a claim about the queries rather than about the rule. A uniform query distribution carries no information the map does not carry, because “uniform over the open cells” is a description of the map. The greedy rule is not failing; it is being asked to extract something from a sample that has nothing in it, and the best it can do is recover what the sample is a sample of. An estimate is a reweighting is the reason the corners are that answer: a landmark repriced map runs downhill to the goal in proportion to how much of the route the landmark sits behind, and on a square with uniform traffic the cells that sit behind the most routes are its extremes.

Queries with a destination #

The interesting case is the one a real system is in. Traffic does not scatter. It runs to a station, a depot, a small number of hubs, and a query log then records something about the world that no amount of looking at the map will reveal.

Twenty queries — the sample size that was 12% worse than the corners under uniform traffic — beats the corners by 29% when every query heads for one cell, and does it on eight maps out of eight. Two destinations is better still, at 98.0 against 138.2. Four destinations begins to give the advantage back, and eight has nearly returned to the uniform case, because eight destinations scattered over a map is most of the way to no destination at all.

Two things move at once across that plate and both matter. The greedy rule improves as the traffic concentrates, which is the expected half. The corner rule gets worse — from 126.3 to 148.5, seventeen per cent — which is the half worth noticing. A rule that reads only the map is not merely uninformed about concentrated traffic; it is mispriced for it, because its landmarks are placed to be behind the average route and concentrated traffic has no average route. The two effects are of similar size, so about half the 29% advantage is the learned rule getting better and about half is the fixed rule getting worse.

The overfitting gap closes at the same time, and that is what makes twenty observations enough. Under uniform traffic twenty queries chosen from left the sample reading 113.3 against a delivered 141.3. Under one destination the same twenty leave the sample reading 100.0 against a delivered 105.7 — a gap of six per cent rather than twenty-five. A sample of twenty routes that all end in the same cell is not twenty accidents; it is twenty draws from a distribution narrow enough that twenty of them describe it, and the rule stops fitting noise because there is much less noise to fit.

The interior landmark is the detail that makes the point. Where the landmarks stand found that farthest-first selection’s fourth landmark lands in the interior and that this is why it loses on every map, and it is right about uniform traffic. With one destination, a cell near the middle of the map lies behind a large share of the routes that actually occur, and a placement rule that has been told what the routes are can use it. The old finding is not overturned; its precondition has been named.

What the preparation costs, in the unit it saves #

A placement is worth what it saves, less what it cost to find. Both are cells expanded, so no exchange rate has to be invented — which is the situation the exchange rate nobody wrote down had to construct by hand for sorting, and which arrives here for free.

The preparation is linear in the sample and the sample is what the rule needs to stop overfitting, so the two requirements pull against each other. Counting the searches understates it, because a search during selection expands cells like any other; counted in cells the same selections cost between 47,000 and 4.9 million.

The two numbers at the ends of that plate are three orders of magnitude apart, and they are the answer to the question the placement essay left open. Under uniform traffic the rule is not merely a draw; it is a draw that costs seven and a half million queries to reach, which for any system that answers fewer than that is a permanent loss. Under concentrated traffic it pays for itself after ten thousand queries, which a routing service reaches in an afternoon.

And the sample size that pays best is not the largest affordable one. Twenty observed queries to one destination pay back after 9,700 queries; two hundred pay back after 87,628, and buy 3.1 cells a query for ten times the preparation. The threshold somebody chose found the same shape in four tuning constants written into real sorting code: the curve near the optimum is flat, so the setting that matters is the one on the steep side, and here the steep side is the small sample.

Why the corners are hard to beat and easy to beat #

The two halves of this page look contradictory and are not. An estimate is a reweighting gives the account that covers both. A landmark estimate is a potential, A* under it is Dijkstra on repriced arcs, and a placement is good to the degree that it makes the arcs along the routes that occur run downhill.

Under uniform traffic “the routes that occur” is every route, so the best placement is the one that makes the map steepest on average, and that is a question about the map’s geometry with a known answer. Under traffic to one destination, “the routes that occur” is a pencil of routes converging on one cell, and the steepest repricing for that pencil is a different placement — one that a rule looking at the geometry cannot name, because the geometry does not contain the destination.

So the amount a query log is worth is the amount by which the traffic differs from the map’s own symmetry. That quantity is measurable before any landmark is placed, and it is the thing a system should look at first. The plate against destinations is a crude sweep of it: at eight destinations the traffic has nearly recovered the map’s symmetry and the query log has nearly stopped being worth reading.

It also explains why the advantage is not monotone in how much is known. The greedy rule at two hundred uniform observations knows the query distribution almost exactly, and what it knows is worthless, because the distribution it has learned is the one the map already implies. Information is worth what it adds to what is already held, and a landmark rule already holds the map. The count somebody chose made the same point about measurement rather than about estimation: six counts of the same run rank ten sorting algorithms six different ways, and the count worth taking is the one that distinguishes the cases at hand rather than the one that is most precise.

What a system with a log should actually do #

Three of the numbers above are enough for a decision, and none of them requires placing a landmark.

Measure the concentration first. Sampling the query log and looking at how far the destinations spread costs nothing next to a single selection round. If the destinations are as spread as the open cells, the plate against destinations says the log is worth nothing here and the corners are the answer — free, immediate, and better than the alternative by a margin no sample size recovers.

If the traffic is concentrated, take a small sample. Twenty observed queries to one destination beat the corners by 29% and repay their preparation after 9,700 queries. Two hundred beat them by 31% and repay after 87,628. The extra 3.1 cells a query cost nine times the preparation, which is the flat-bottom shape the flat bottom of a shallow curve found in a different parameter entirely: near the optimum the objective barely moves, so the setting to argue about is the one on the steep side, and here that is the difference between one observation and twenty rather than between twenty and two hundred.

Report the cost on queries the choice has not seen. The lower line on the first plate is the number a selection procedure hands back if it is asked what it achieved, and it is 25% optimistic at twenty observations and a factor of twenty-five optimistic at one. A placement is worth reporting only against queries it was not fitted to.

What is not measured here #

One family of maps. Every map is 50 × 50 with 28% of its cells removed and step costs from one to nine. A map with a genuine road network — long corridors, few junctions — would change what a corner is worth and probably narrow the gap, since a corridor map has few distinct routes whatever the query distribution.

A destination set that does not move. The hubs are fixed for the whole run, so the sample and the fresh queries are drawn from the same distribution. A system whose traffic shifts between morning and evening is choosing landmarks from a log that describes a distribution it will not face, and the preparation would have to be repaid each time it shifted. The break-even figures above are therefore best cases for the learned rule.

Four landmarks and twenty-five candidates. The candidate lattice is coarse enough that the greedy rule is choosing between twenty-five cells, not 1,800. A finer lattice would find better placements and multiply the preparation by the same factor, which moves both numbers in the payback calculation in the same direction and makes the break-even worse, not better.

Greedy, not optimal. Nothing here computes the best four cells. A greedy set can be arbitrarily worse than the best set, and the plate showing each round’s gain is consistent with a fourth landmark that a different first choice would have made redundant.

Cells expanded, not time. The unit throughout is cells expanded, as the cells are not the cost argued it should not be taken to be. Four landmark tables over 2,500 cells are 10,000 exact distances held in memory, and measuring what an algorithm keeps is the argument for reporting that second axis: every placement on this page holds exactly the same amount, so the comparison is fair, and the comparison with a system holding no tables at all is not made here.

Still open: a rule that knows when to stop reading the log #

The break-even arithmetic assumes the selection runs once and the placement is kept. A system whose traffic drifts faces a schedule instead: reread the log, rechoose, pay the preparation again. The plate against destinations says what is at stake — a placement fitted to one destination is worth 29% on that destination and is presumably worth less than the corners on a different one — but nothing here measures what it is worth after the traffic has moved.

The measurement that follows fixes a placement from a log with one destination, then moves the destination by a stated distance and asks how the advantage over the corners decays with that distance; and then, on a stream whose destination drifts continuously, prices two policies against each other — rechoose every so many queries, and rechoose when the mean cells expanded rises by a stated fraction above what the placement achieved when it was new. The second needs no drift model and costs one counter, and the question is how much of the first’s advantage it keeps. That is the question a system with a query log actually has, and neither plate on this page answers it.