Choosing a Grid Cell Size for OSM Spatial Hashing

A spatial hash is the simplest index that works, and its entire behaviour is decided by one number nobody measures. Too large and every query scans thousands of irrelevant features; too small and the index is mostly empty cells and pointer chasing.

Prerequisites

Conceptual minimum

A spatial hash maps each feature to one or more integer cell coordinates and stores it in a dictionary keyed on them. A query computes the cells its search area touches and examines only the features in those cells.

Two costs pull in opposite directions. Cells examined per query grows as the cell shrinks, because a fixed radius covers more of them. Features examined per cell grows as the cell enlarges, because more features fall inside. Total work per query is roughly their product, and it has a minimum.

The useful rule is that the cell should be comparable to the query radius. Substantially smaller, and each query touches a large block of cells whose lookup overhead dominates. Substantially larger, and each cell holds far more features than the query needs. A cell of roughly one to two times the radius keeps both terms small.

Density matters because it decides what “far more features” means. A cell size that is ideal for a rural extract puts tens of thousands of features in a single cell in a city centre.

Total work per query as the cell size varies, for a fixed search radius Five cell sizes relative to a fixed query radius, with the approximate total work per query. At a tenth of the radius the query touches hundreds of cells and lookup overhead dominates. At half the radius it touches around twenty cells and the work is much lower. At one times the radius the work is near its minimum. At four times the radius each cell holds many more features than needed and work rises again. At sixteen times the radius nearly every query scans a large share of the dataset. Work per query against cell size, radius held fixed cell = 0.1x radius lookup dominates cell = 0.5x radius much better cell = 1x radius near the minimum cell = 4x radius scanning dominates cell = 16x radius scans most of it The curve is flat near its minimum, so any cell between about half and twice the radius performs within a small factor of the best.
That flatness is why measuring once is enough: the penalty for being somewhat wrong is small, and for being very wrong is large.

Runnable solution

python 
from __future__ import annotations

import logging
import math
from collections import defaultdict
from dataclasses import dataclass

import numpy as np

logging.basicConfig(level=logging.INFO, format="%(levelname)s: %(message)s")
logger = logging.getLogger("osm.index.hashgrid")


@dataclass(frozen=True)
class GridStats:
    cell_size_m: float
    occupied_cells: int
    empty_ratio: float          # of the bounding box's cells, how many are empty
    median_per_cell: float
    p99_per_cell: float
    max_per_cell: int


def build(points: np.ndarray, cell_size_m: float) -> dict[tuple[int, int], list[int]]:
    """Map each point index into an integer cell. Points are (n, 2) metres."""
    cells = np.floor(points / cell_size_m).astype(np.int64)
    grid: dict[tuple[int, int], list[int]] = defaultdict(list)
    for index, (cx, cy) in enumerate(cells):
        grid[(int(cx), int(cy))].append(index)
    return grid


def stats(points: np.ndarray, cell_size_m: float) -> GridStats:
    grid = build(points, cell_size_m)
    counts = np.array([len(v) for v in grid.values()])
    extent = points.max(axis=0) - points.min(axis=0)
    total_cells = max(1.0, math.prod(np.ceil(extent / cell_size_m) + 1))
    result = GridStats(
        cell_size_m=cell_size_m,
        occupied_cells=len(grid),
        empty_ratio=1.0 - len(grid) / total_cells,
        median_per_cell=float(np.median(counts)),
        p99_per_cell=float(np.percentile(counts, 99)),
        max_per_cell=int(counts.max()),
    )
    logger.info("cell %7.0f m: %7d occupied, %4.0f%% empty, median %5.1f, "
                "p99 %7.0f, max %7d", result.cell_size_m, result.occupied_cells,
                result.empty_ratio * 100, result.median_per_cell,
                result.p99_per_cell, result.max_per_cell)
    return result


def recommend(points: np.ndarray, query_radius_m: float,
              target_per_cell: int = 16) -> float:
    """Start from the radius, then adjust for measured density."""
    # Density from the median occupancy at a trial cell equal to the radius.
    trial = stats(points, query_radius_m)
    if trial.median_per_cell <= 0:
        return query_radius_m

    # Scale so a typical cell holds about `target_per_cell` features. Area
    # scales with the square of the size, hence the square root.
    scale = math.sqrt(target_per_cell / trial.median_per_cell)
    # Stay within half to twice the radius: outside that, one term dominates.
    scale = min(max(scale, 0.5), 2.0)
    chosen = query_radius_m * scale
    logger.info("radius %.0f m, median %.1f per cell -> recommending %.0f m",
                query_radius_m, trial.median_per_cell, chosen)
    return chosen


def sweep(points: np.ndarray, query_radius_m: float) -> list[GridStats]:
    return [stats(points, query_radius_m * f)
            for f in (0.25, 0.5, 1.0, 2.0, 4.0)]


if __name__ == "__main__":
    rng = np.random.default_rng(0)
    # A dense core plus a sparse surround: the shape real OSM data has.
    dense = rng.normal(0, 400, size=(40_000, 2))
    sparse = rng.uniform(-20_000, 20_000, size=(10_000, 2))
    sample = np.vstack([dense, sparse])
    sweep(sample, query_radius_m=250.0)
    recommend(sample, query_radius_m=250.0)

Step-by-step walkthrough

  1. Start from the query radius. It is the only number that relates the index to the work it will actually do, and a cell comparable to it is close to optimal before any measurement.
  2. Measure median occupancy, not mean. OSM density is extremely skewed; the mean is dragged upward by a handful of city-centre cells and describes no typical cell at all.
  3. Scale by the square root. Cell area grows with the square of the size, so halving the occupancy means dividing the size by the square root of two rather than by two.
  4. Clamp to half and twice the radius. Outside that band one of the two cost terms dominates whatever the density says, so the density adjustment is a refinement rather than an override.
  5. Report the high percentile and the maximum. The median tells you the common case; the ninety-ninth percentile tells you what a city-centre query costs, which is the number that actually shows up in a latency graph.
  6. Watch the empty ratio. A grid that is ninety-nine percent empty is spending memory on a structure that a tree would represent far more compactly — a signal to reconsider the index choice entirely.
  7. Sweep before committing. Five trial sizes cost seconds and produce a curve whose flat region tells you how much the choice actually matters for your data.
The two failure modes and the statistic that reveals each Three panels. A cell that is too small produces a grid where almost every cell is empty and each query touches hundreds of them, revealed by a very high empty ratio and a very low median occupancy. A cell that is too large produces a grid where city-centre cells hold tens of thousands of features, revealed by a ninety-ninth percentile occupancy far above the median. A well-sized cell shows a moderate empty ratio and a high percentile within about an order of magnitude of the median. Two failures, two statistics, one healthy middle Too small Almost all cells empty Median occupancy near one Queries touch hundreds Lookup overhead dominates Too large City cells enormous p99 far above median Queries scan thousands Filtering dominates Well sized Moderate empty ratio p99 within ~10x median Queries touch a handful Both terms small The ratio between the median and the high percentile is the single most informative number, because it measures the skew directly.
Reporting only the mean occupancy hides both failures, because a skewed distribution's mean sits between them.
The four measurements that decide a cell size Four steps. The trial step builds the grid once at a cell size equal to the query radius, which is already close to optimal. The measure step records the median occupancy, the ninety-ninth percentile and the proportion of empty cells. The adjust step scales the size by the square root of the ratio between the desired and measured occupancy, clamped to stay within half to twice the radius. The confirm step times real queries across several sizes and checks that the cost curve has a minimum near the chosen value. Trial, measure, adjust, confirm trial cell equals radius already close measure median, p99, empty never the mean adjust square-root scaling clamped to a band confirm time real queries look for the dip The whole procedure takes seconds on a sample and replaces a number that is otherwise chosen by habit and never revisited.
Skipping the last step is common and usually fine, because the curve is flat — but it is the only step that measures reality.

Verification

  • The sweep has a visible minimum. Time real queries at each trial size; the curve should dip rather than being monotonic.
  • The high percentile is bounded. A ninety-ninth percentile occupancy in the tens of thousands means dense areas will dominate latency.
  • The empty ratio is reasonable. Above about ninety-five percent empty, a tree structure is probably the better index.
  • Dense and sparse areas both behave. Time queries in a city centre and in open country; the difference should be a factor, not an order of magnitude.
  • Recomputing on new data agrees. Run the recommendation on a second extract from the same region; the answer should be close.

Common errors and fixes

Symptom Root cause One-line fix
Queries slow only in cities Cell sized from mean occupancy Size from the median and check the high percentile
Index memory far exceeds the data Cell far smaller than the radius Enlarge towards the query radius
Every query scans thousands Cell far larger than the radius Shrink towards the query radius
Cell size behaves differently by latitude Grid built in degrees Build the grid in a metric projection
Recommendation swings between runs Sample too small or unrepresentative Sample across dense and sparse areas
Tuning has no effect Query cost dominated by something else Profile before tuning the index
Grid mostly empty Point distribution very clustered Consider a tree index instead of a hash

Specification reference

A uniform spatial hash partitions the plane into equal cells and assigns each object to the cell containing it, giving constant-time insertion and a query cost proportional to the number of cells overlapping the search region multiplied by their occupancy. Performance therefore depends on the relationship between cell size, query extent and object density rather than on the structure itself. See Spatial Indexing for OSM Extracts for how this compares with tree-based alternatives.

Frequently Asked Questions

Why size the cell from the query radius rather than the data?

Because the radius is what determines how many cells a query touches, and that term is one of the two halves of the cost. The data’s density determines the other half, and it enters as a refinement — a scaling factor that adjusts the radius-derived size so a typical cell holds a sensible number of features. Starting from the data alone gives no relationship to the work queries actually do.

Should I use the mean or the median occupancy?

The median, and report the high percentile alongside it. OSM feature density is extremely skewed: a handful of city-centre cells hold orders of magnitude more than everything else, which drags the mean to a value no actual cell resembles. The median describes the typical cell and the ninety-ninth percentile describes the cell that will dominate your latency graph, and you need both.

When is a hash grid the wrong structure?

When the distribution is very clustered, which OSM’s often is. A grid sized for city centres wastes enormous memory on empty cells across open country, and one sized for the average performs badly in both. A tree-based index adapts to density automatically and is usually the better choice for continental extracts; a hash grid shines on bounded areas with reasonably even distribution.

Does the cell size need to be a round number?

No, and choosing round numbers is mildly harmful because it encourages picking from habit rather than from measurement. The cost curve is flat near its minimum, so any value within about a factor of two of the ideal performs within a small factor of the best. What matters is being in that band, which requires measuring rather than being tidy.

Up one level: Spatial Indexing for OSM Extracts.