Advanced: Proximity Search

“Find the 20 nearest restaurants,” “show drivers within 2 km,” “who is nearby to match with” — proximity search sits at the heart of Yelp, Uber, DoorDash and Tinder. It looks trivial: you have a table of places with latitude and longitude, and you want the ones close to a point. But the naive approach collapses the moment you have real data, and the fix — spatial indexing — is a genuinely different idea worth having in your toolkit.

In the interview: when a question involves “near me,” “within X km,” or a map, say early that you will index by geospatial cell rather than scanning and computing distance. Then pick a scheme (geohash or S2) and explain the cell-plus-neighbours query. That immediately shows you know this is a specialised problem.

Why the naive approach fails

The obvious solution is to compute the distance from the user to every place and keep the closest ones:

SELECT * FROM places
ORDER BY haversine(lat, lng, :user_lat, :user_lng)
LIMIT 20;

This is O(n) per query — it touches every row and runs a trigonometric distance for each. With a few hundred rows it is fine; with tens of millions of places and thousands of queries per second it is hopeless, and the distance function means you cannot use an ordinary index.

A tempting half-fix is a bounding box: WHERE lat BETWEEN ... AND lng BETWEEN .... A standard B-tree index can satisfy one of those ranges, but not both at once — latitude and longitude are independent dimensions, and a one-dimensional index cannot capture two-dimensional closeness. Two points can share almost the same latitude yet be a thousand kilometres apart. We need an index that understands that nearby in space means nearby in the index.

The core idea: turn 2-D space into sortable cells

The whole trick is to divide the map into cells and give each cell an id, chosen so that cells close in space have ids close in sort order. Then “near me” becomes “the same cell, and the cells next to it” — a cheap range lookup instead of a full scan.

Geohash

Geohash encodes a (latitude, longitude) pair into a short base-32 string by repeatedly bisecting the world. The first character picks a large region, the next narrows it, and so on — more characters mean a smaller, more precise cell:

The key property is the shared-prefix rule: two locations whose geohashes start with the same characters are in the same region. tdr1y and tdr1z are neighbours; tdr1… and 9q8y… are on different continents. So to find everything near a point, you compute its geohash and do a prefix/range scan — something an ordinary B-tree index on the geohash string handles beautifully.

S2 and quadtrees

S2 (Google’s library, used by Uber and others) projects the sphere onto a cube and uses a Hilbert curve to number cells, which preserves locality even better than geohash and avoids some of its distortion near the poles. The idea is the same: a 64-bit cell id where numeric closeness implies spatial closeness.

QuadTrees take a different tack. Instead of fixed cells, a quadtree recursively splits any cell that contains more than a threshold number of points into four quadrants. Sparse areas (an ocean, a desert) stay as big cells; dense areas (Manhattan) subdivide deeply. This adapts to density, so each leaf holds a bounded number of points — handy when places are wildly unevenly distributed.

The query, end to end

With a cell index in place, a “nearby” query has three steps:

1. Find candidate cells. Compute the viewer’s cell at a precision matching the search radius, then gather that cell plus its eight neighbours. The neighbours matter because the user might be standing at the edge of their cell — the nearest restaurant could be just across the boundary in an adjacent cell. This is the boundary problem, and forgetting it is the classic bug.
2. Hydrate candidates. Pull the places in those cells from the index. This is now a small set — tens or hundreds, not millions.
3. Filter and rank exactly. Compute the true haversine (great-circle) distance for each candidate, drop anything outside the real radius, and sort by distance — or re-rank by a blend of distance, rating and price, which is what Yelp actually does.

If a cell is too sparse to return enough results, widen the search by using a shorter prefix (a bigger cell) or expanding the neighbour ring.

Tooling

You rarely implement this from scratch in an interview — name the tool and move on:

• Redis GEO — GEOADD / GEOSEARCH store points on a sorted set keyed by geohash; great for hot, in-memory “drivers near me” with fast updates.
• PostGIS — the PostgreSQL extension with proper geometry types and GiST spatial indexes; the default when geo data lives alongside relational data.
• Elasticsearch geo — geo_point with geo_distance queries, good when proximity combines with text/attribute filtering (search “pizza” near me, open now).

Dynamic objects: moving drivers

For static places (restaurants) you index once. For moving objects (ride-share drivers, delivery riders) each location ping is a write that re-indexes the object into a possibly new cell. The pattern is an in-memory geo index (Redis) updated on every ~4-second location update, with the rider matching service querying “drivers in these cells.” The write rate is high, which is exactly why you keep this index in memory and separate from the system of record.

Key Takeaways

1. Never scan-and-compute-distance. That is O(n) per query and cannot use an index. Spatial indexing is a distinct technique — recognise the “near me” signal and reach for it.

2. Index by cell so that nearby-in-space is nearby-in-index. Geohash (shared-prefix strings) and S2 (Hilbert-curve cell ids) both turn 2-D location into a sortable key a B-tree can range-scan.

3. QuadTrees adapt to density by subdividing crowded regions, bounding how many points fall in any leaf — useful when places cluster unevenly.

4. Query = viewer’s cell + its 8 neighbours, then exact distance. Always include neighbouring cells to handle the boundary problem, then filter by true haversine distance and re-rank by rating or price.

5. Use the right tool: Redis GEO for fast in-memory “near me,” PostGIS for geo-plus-relational, Elasticsearch for geo-plus-search.

6. Moving objects re-index on every update. Keep the geo index for drivers/riders in memory and separate from the durable store, because the write rate is high.