The query a fast path actually answers

Fifteen rungs of this ladder price what a stored coordinate means: what it refers to, what an area computed from it is, what a segment claims, what a number stored beside it says.

None of them asks what it is searched with.

No index answers the question it is asked #

A spatial index — an R-tree, a quadtree, a grid — answers exactly one kind of question, and the whole value of it is that it answers that question without looking at most of the data: which stored objects lie inside this rectangle of stored coordinates. It has no notion of a distance on the ground, and it could not have one, because it never sees the projection.

So a query for “everything within R kilometres of here” is turned into a rectangle before it reaches the index, by arithmetic that lives in the application. The candidates come back, an exact test filters them, and the answer is returned.

The exact test is the part everybody is confident about — it computes a real ground distance, on the sphere, with the right formula — and it is not the part that matters. A filter can only remove candidates. Anything the box excluded is silently absent from the answer, and nothing downstream can tell.

That asymmetry is the whole vulnerability. A box that is too large costs work and nothing else, because the filter removes the strangers; a box that is too small costs correctness, and there is no stage of the pipeline whose job it is to notice. So the arithmetic that sizes the box has a bound it must satisfy in one direction and not the other, and it is written as an equality.

The arithmetic, and why it is wrong #

The ordinary way to size the box is to convert R into projected units using the scale factor at the query point — which is what a single stored constant of metres-per-unit amounts to, and what every projection library will hand back if asked.

That is exactly right at the query point and wrong everywhere else in the box, because the scale factor varies across it. On the side where the map is smaller, the box covers less ground than R, and true neighbours fall outside.

Two columns, and they say different things. The share is how much of the answer’s boundary is outside the box; the overshoot is how far outside, as a fraction of the box’s own half-width, which is what a safety margin would have to cover.

The control is the equator #

On the equator a normal-aspect cylindrical projection’s scale factor is stationary — its derivative in latitude is zero — so a box sized at the centre is sized correctly across the whole query, and the miss is zero to the last digit.

That is the check that makes every other number here a measurement. If the equator lost anything, the effect would be the shape of the box rather than the variation of the scale, and the diagnosis would be wrong.

The second check is the repair. A box sized from the worst scale anywhere in the query’s own extent — a ten per cent inflation at four hundred kilometres — misses nothing, at any latitude tried. So the failure is the arithmetic and not the index.

Conformality bounds the damage, and nothing else does #

The structure in that column has a one-line cause. A single metres-per-unit constant is a fair summary of the scale only where the two principal scales are equal, which is what conformality means. On a conformal projection the box is the right shape and only the wrong size, and the error is the variation of one number. On anything else the box is the wrong shape: the plate carrée at 55° north is at scale 1.00 along the meridian and 1.74 along the parallel, and a box sized by the mean of those is too short east-and-west by a third.

Three fifths of the answer’s boundary, on a projection chosen for being equal-area. That is a real configuration — a national dataset stored in an equal-area system for analysis, queried by radius — and the failure is invisible in every test that checks the results it does return.

The same query, drawn where the failure is worst #

That figure is the argument in one picture, and it says why conformality is the property that matters here rather than any of the ones a system is usually chosen for. A stored plane in which the query is round needs a box that is square; a stored plane in which the query is a two-to-one ellipse needs a box that is two to one, and nothing in the pipeline knows the shape.

Why this survives testing #

Three reasons, and each is a general one.

A test with a small radius passes. At twenty kilometres the loss is 5.7 per cent of the rim and 0.34 per cent of the box, and a test fixture built at a scale a developer can check by hand is a test fixture in the regime where the effect is smallest.

A test at low latitude passes. Half the world’s spatial data is developed in one hemisphere and deployed in both. The measurement is zero on the equator and small in the tropics, and a dataset developed on one region and deployed on another crosses that without a signal.

And there is nothing to assert. The query returns some answer, every returned object is genuinely within the radius, and the count is plausible. A false negative has no representation in the output — which is the same shape of defect as the fifty-two generator pages nobody linked and as every omission this collection has met: an error that consists of something not being there.

The test that would catch it is a comparison against a brute-force scan, on a query large enough and high enough to matter — a thousand queries, each answered twice, with the two answers compared as sets rather than as counts. That is one afternoon and it is not in anybody’s suite, and the reason it is not is the third point above: nobody writes a test for an output that looks right.

What to do instead #

Three repairs, in increasing order of correctness.

Inflate the box, which is the cheapest of the three and the only one that needs no change to the index. Size it from the worst scale factor over the query’s extent rather than at its centre, which is a bound that can be computed from the projection and costs a few per cent more candidates — ten per cent at four hundred kilometres on Web Mercator, which is the measured inflation and is what the refusal above uses. The exact filter then removes them, so the only cost is work.

Build the box on the sphere. Compute the query’s true bounding box in latitude and longitude — which has a closed form, and is what a range ring’s own extent is — and project its corners, remembering that the projected corners are not the projected box’s corners unless the edges are straight in the plane. That is correct rather than bounded, and it is barely more arithmetic.

Or index the sphere, since an address is an area and a cell system’s addresses nest. A hierarchical cell system on the sphere answers a disc query directly, with no plane anywhere, which is what a cell system is for and is why the big geospatial systems have one.

The first is what most systems should do and none appears to. The general form of the advice is the field’s own rule: the operation decides the coordinate system, and a nearest-neighbour search is an operation like any other.

What the failure costs, in the terms an application uses #

The share of a rim is the right measurement and it is not the number an application cares about, so it is worth converting.

For objects spread uniformly over the ground, the ones at risk are those in the annulus between the largest circle the box contains and the query circle itself. At 55° north with a two-hundred-kilometre radius the box’s inscribed circle is 97.6 per cent of the query radius, so the annulus is 4.8 per cent of the query’s area — and about a tenth of that annulus is in the excluded corners, giving roughly half a per cent of a uniform population missed.

Half a per cent of a nearest-neighbour result is not a rounding error and is not a catastrophe. What makes it worth an essay is where it falls: entirely at the edge of the query, which is exactly where the marginal cases are and exactly where an answer is most likely to be acted on. A search for the nearest facility that silently omits the boundary cases returns a facility that is not the nearest, and the whole of the query’s purpose is in that annulus.

On the Lambert cylindrical the same arithmetic gives an inscribed circle at 57 per cent of the radius, and the missed population is not half a per cent of anything.

The same failure at the other end of the pipeline #

The candidate box is one place a query is turned into a rectangle, and it is not the only one.

A tile request is a box. A map client asking a server for the data in a viewport sends the viewport’s bounds in the stored plane, and anything whose own bounding box misses that rectangle is not returned — so a feature that is inside the view on the ground and outside the box in the stored coordinates is silently absent from the drawn map. The failure is the same shape and the diagnosis is the same: a rectangle in one plane standing in for a region in another.

A spatial join is two boxes. Joining two layers by proximity uses one layer’s boxes to probe the other’s index, so the error compounds: each side contributes its own scale variation, and the pair is lost if either box misses.

And a clustering is a box per cluster. Anything that groups by a bounding rectangle in stored coordinates inherits the whole of it.

What the three have in common is that the rectangle is not a lie anybody tells; it is the only thing the index can be asked. What varies is whether the arithmetic that produced it was conservative, and in none of the three does the pipeline check.

Where the model stops #

The population here is the query’s own rim — the places at exactly the query radius — because those decide the answer: anything comfortably inside the radius is inside the box too. A real dataset’s objects are not on the rim, so the fraction of objects lost depends on how they are distributed, and the rim share is an upper bound on it rather than a prediction.

The box is axis-aligned in the stored coordinates, which is what every index uses. An index that stored a rotated box, or a disc, would have a different and generally smaller error, and none does.

And the scale used is the areal mean. A library that returned the two principal scales separately would allow a rectangle sized correctly in each direction, which fixes the shape error and leaves the variation error — taking the Lambert cylindrical’s 61 per cent down to something like Mercator’s 8. Nobody’s metresPerUnit returns two numbers.

The generalisation #

An acceleration structure answers a different question from the one it accelerates, and the difference is the application’s to bound.

That is not a statement about geography. Any index — a hash on a rounded key, a bloom filter, a bounding volume, a nearest-neighbour tree in a learned embedding — answers a cheap question whose answer is meant to contain the expensive question’s. When it does, the structure is conservative and the exact filter makes it correct. When the containment fails, the structure is fast and wrong, and the wrongness is a false negative, which has no representation in any output.

The discipline this asks for is one line long: for every fast path, state the containment it relies on and check it. On this one the containment is that the candidate box covers the query’s ground extent, and it does not.

Who found it, and when #

The candidate-box pattern is as old as spatial indexing — Guttman’s R-tree is 1984 and the filter-and-refine framing was standard within a few years — and the requirement that the filter be conservative is stated in every treatment of it.

What is not standard is checking it against a projection. The literature’s examples are in one plane with one unit, where a bounding box in stored coordinates is a bounding box on the ground; the moment the stored plane is a map of a sphere the containment becomes a claim about a scale factor, and the arithmetic that turns a radius into a box is written in application code where nobody is thinking about projections at all.

A filter’s bound is provable, so it should be proved #

The discipline the rung asks for is one line, and it is worth saying why proving it is both possible and preferable to testing it.

Conservativeness is a mathematical property, not an empirical one. The claim is that the candidate set contains every possible answer, and that follows from a bound on the scale factor over the query’s extent — a quantity the projection supplies in closed form. Nothing about the data enters, so the claim can be established once for a projection and a latitude range rather than sampled.

Testing it is nearly hopeless, and the essay’s own account of why this survives testing says so. A test finds a failure only when a query happens to sit where the shortfall exceeds the margin and an answer happens to lie in the lost sliver. Both are rare, both depend on the data, and a suite that passes proves that neither coincided today.

The safe direction is known and cheap. A filter that is too generous costs time and returns the right answer; one that is too tight loses results with no error and no log line. So the repair is to inflate the candidate box by the maximum scale factor over the query’s own latitude span — a factor computable from the projection, applied at query time, costing one evaluation and some wasted candidates.

And the wasted candidates cost almost nothing, which is the argument that should end the discussion. The refine step already re-tests every candidate exactly; enlarging the filter adds candidates that the refine step discards. The price of correctness here is a slightly longer list passed between two steps that were already there.

A reviewer can also ask the narrower version, which needs no theory: what happens to this box at eighty degrees north.

The general contract is worth stating in the form a reviewer can apply. Every fast path replaces an exact test with a cheap one, and the cheap one is only legitimate if it never excludes a true answer. That is a statement about the cheap test, it is provable, and a fast path whose author cannot say what the bound is has not got a fast path — it has an approximation with no error term.

Where the ladder goes next #

Sixteen rungs price a stored coordinate, its attributes, its edges and now its index. What none of them prices is the schema: a dataset declares a coordinate system in its metadata, the declaration is a string, and every failure this ladder has measured happens twice as fast when the string is wrong.