Sizing Hash Cells from Fence Size Distributions

A spatial hash trades the adaptivity of a tree for a constant-time lookup, and the price of that trade is a cell size that has to be chosen in advance. The choice is genuinely hard because geofence sizes are not merely varied but scale-free: a real fence set contains 4 m parking bays and 40 km municipal boundaries, four orders of magnitude apart, and no single cell size serves both. Too small and a large fence occupies thousands of cells; too large and a query returns every fence in a neighbourhood. This page sits under dynamic spatial hashing strategies within Spatial Indexing for Real-Time Checks.

Concept and specification #

The two costs move in opposite directions with cell size $c$. A fence of extent $w$ occupies about $(w/c+1{)}^2$ cells, so insertion cost and index memory grow as $c$ shrinks. A query returns every fence registered in the cell containing the point, so candidate count grows as $c$ grows — roughly with the density of fences whose extent is below $c$.

$$E[\text{cells per fence}]\approx {\left(\frac{w}{c}+1\right)}^2,E[\text{candidates}]\approx \rho \cdot c^2+n_{\text{large}}$$

Minimising their sum for a single fence size gives the familiar rule of thumb that the cell should be about the mean fence extent. The rule fails on a real distribution because the mean is meaningless for a scale-free set — the mean extent of a fence set containing parking bays and municipalities is dominated by the municipalities and is wrong for 90% of the fences.

Measured over 1.2M fences from a production platform:

The insight the table makes concrete is that the two costs are borne by different populations. The candidate count is dominated by the small and medium fences, which are numerous; the cell occupancy is dominated by the large ones, which are few. A single cell size cannot be right for both, and the fix is not a better single size but a hierarchy: several grids at different resolutions, each holding the fences whose extent suits it.

$$\text{level}(w)=\lceil {\log }_2\frac{w}{c_0}\rceil$$

A query then probes one cell per level — three or four lookups instead of one — and each level returns only fences of a scale for which its cell size is appropriate.

Step-by-step implementation #

1. Measure the extent distribution before choosing anything. Compute each fence’s maximum bounding-box side and histogram the base-2 logarithm. The number of populated octaves is the number of levels the hierarchy needs; three or four covers most platforms.

2. Assign each fence to the level whose cell is just larger than its extent. That guarantees a fence occupies at most four cells at its own level, whatever its position.

from __future__ import annotations
from collections import defaultdict
import math

class HierarchicalHash:
    """One grid per octave of fence size. A fence lives at exactly one level."""

    __slots__ = ("base_m", "levels", "grids")

    def __init__(self, base_m: float = 64.0, levels: int = 4) -> None:
        self.base_m, self.levels = base_m, levels
        self.grids: list[dict[tuple[int, int], list[int]]] = [
            defaultdict(list) for _ in range(levels)
        ]

    def _level_for(self, extent_m: float) -> int:
        lv = max(0, math.ceil(math.log2(max(extent_m, 1.0) / self.base_m)))
        return min(lv, self.levels - 1)

    def _cell_m(self, level: int) -> float:
        return self.base_m * (2 ** level)

    def insert(self, fence_id: int, minx: float, miny: float,
               maxx: float, maxy: float) -> None:
        lv = self._level_for(max(maxx - minx, maxy - miny))
        c = self._cell_m(lv)
        for gx in range(int(minx // c), int(maxx // c) + 1):
            for gy in range(int(miny // c), int(maxy // c) + 1):
                self.grids[lv][(gx, gy)].append(fence_id)

    def query(self, x: float, y: float) -> list[int]:
        out: list[int] = []
        for lv in range(self.levels):
            c = self._cell_m(lv)
            out.extend(self.grids[lv].get((int(x // c), int(y // c)), ()))
        return out

3. Keep the coordinates in metres, not degrees. A grid in degrees has cells that are 111 km tall everywhere and between 111 km and nothing wide depending on latitude, so its cell size varies by a factor of two across a continent. Project first, using the frames described in geodesic vs planar distance for fence tests.

4. Cap the level count from the largest fence, not from ambition. Every level costs one dictionary lookup per query whether or not it holds anything, so a hierarchy sized for a hypothetical continental fence charges every query for a level that is almost always empty. Four levels covering 64 m to 512 m to 4 km to 32 km handles 99.6% of the distribution; put the remaining handful in the top level and accept their cell occupancy.

5. Handle the outliers separately rather than deepening the hierarchy. The 0.4% of fences over 20 km are better held in a small linear list that every query scans — 4,800 fences at a bounding-box test each is 19 µs, which is worse than an index but is paid on a tiny population and avoids a fifth level for everyone.

6. Re-measure quarterly. The extent distribution moves as customers change: a platform that adds a logistics customer acquires thousands of large fences overnight, and a level boundary that was well placed becomes badly placed.

Benchmark and verification #

Measured at 25k queries/sec against 1.2M fences with the extent distribution above:

The hierarchy is better than every single grid on every column simultaneously, which is unusual and is the point of the page: it gets the candidate count of the finest grid at a twentieth of its memory, because each fence is registered once at a level where it fits rather than tiled across a grid too fine for it.

The single-grid rows show how sharply the trade bites. Going from 50 m to 1 km cells cuts memory 26× and multiplies the candidate count by nearly 200, which turns a 4 µs query into an 84 µs one — the exact-containment work downstream then dominates everything, and the index has stopped doing its job.

Verify the level assignment by exporting a histogram of cells-occupied-per-fence. In a correctly configured hierarchy the P99 is 4 and the maximum is small; a long tail means fences are landing at a level too fine for them, which is usually a units bug — an extent computed in degrees against a base in metres.

Failure modes and edge cases #

The dense-cluster row is the failure mode a uniform grid cannot escape by sizing alone. An airport, a port or a city centre can hold thousands of fences of similar size inside one cell, and no global cell size fixes it — the density is local. The standard remedy is to promote an over-full cell to its own subgrid, which is the adaptive step that turns a hash into something closer to a quadtree, and it is worth doing only for the handful of cells that need it. The threshold that works in practice is a few hundred entries per cell, above which the linear scan of the cell’s list costs more than the extra lookup.

One last note on the outlier list. Scanning 4,800 large fences per query sounds wasteful and is not, because those fences are exactly the ones whose bounding boxes are enormous and therefore match almost every query anyway — putting them in a grid would register each in thousands of cells to reach the same result. The list is honest about the fact that a continental fence has no useful spatial index entry, which is the same observation the antimeridian split makes from a different direction in antimeridian and pole-crossing geofences.

Related #

• Dynamic Spatial Hashing Strategies — the parent topic and the adaptive splitting this hierarchy complements.
• Comparing Geohash vs H3 for Low-Latency Routing — hierarchical cell systems with the levels built in.
• Quadtree vs R-Tree Performance Analysis — the tree structures that adapt to density without a level choice.