Nearby search

Grids, geohash cells and quadtrees, and the edge problem that loses results.

On the roadmap:Staff Engineer · step 3: Maps and location

Starterabout 10 to 15 min6 experiments

Experiments

New here? A few short steps show what happens, one at a time.

Settings

How to search

Measure the distance to every place. Always right, and slower as the list grows.

Places on the map50,000

Search distance2% of the map

Places checked per search

50,000

Results found

278

Results missed

Cells or areas opened

none

Every search measures 50,000 distances to find about 278 places. It is exact, and it does not scale.

One search, close to a cell edge

Found: inside the circle and looked at
Missed: inside the circle, never looked at
Checked, but outside the circle (wasted work)
Never touched
Shaded squares are the cells or areas that were opened. The dashed circle is the search.

In plain words

Finding the places within a distance of a point is a search problem on a map. Checking every place works for a few thousand. For millions you cut the map into cells, or into areas that adapt to how crowded they are, and only look nearby. The trap is the edge of a cell, where a place just across the line is easy to miss.

Why it matters

Every ride-hailing, delivery and dating app asks this question all the time. The answer has to be fast, and it has to be right near the edges, which is where a naive grid fails. Here you can see how much work each method does, and watch the places it misses.

How real systems do it

The simulation is a simplified model. Here is what production systems add or do.

A geohash turns a location into a short string where places that are close share a long prefix. Searching a geohash cell and its eight neighbours is the standard way to avoid the edge problem. Redis GEO commands use a geohash internally.
Uber's H3 divides the world into hexagons, which have the useful property that all six neighbours are the same distance away. Google's S2 library covers the sphere in cells along a space-filling curve and is used by many mapping systems.
PostGIS and other spatial databases index points with R-trees, which group nearby shapes into rectangles, and quadtrees and k-d trees are used in memory.
Real systems add a final step: the cells give a short list of candidates, and then the exact distance is computed for each. The cells only have to be good enough to make the list short.