Nearby Places

Nearby Places answers "what's around me?" — restaurants, ATMs, shops within a radius of a point, often with filters (open now, cuisine, rating). Unlike Ride Sharing, the points are mostly static (a restaurant doesn't move), so this is a cleaner, read-heavy showcase of Proximity Search: the whole game is the geospatial index.

1. Requirements

Functional:

• Given a location and radius, return places within it.
• Filter by attributes (category, open now, rating) and sort by distance.

Non-functional:

• Fast — sub-100ms geo queries.
• Read-heavy — far more searches than updates (places change rarely).
• Scale — hundreds of millions of places; high query volume.
• Data is mostly static, so cache aggressively.

2. Why a normal index fails

The naive query — "all places where distance(place, me) < R" — must compute distance to every place, an O(n) scan. A B-tree index on latitude and longitude separately barely helps: it can bound a box on one axis, but "within a box" across both axes still returns a huge strip to filter. 2D proximity needs a 2D-aware index (Proximity Search).

3. The geospatial index

Two standard structures, both turning 2D nearness into something indexable:

• Geohash — encode a lat/long into a short string where a shared prefix means spatial proximity (nearby points share a prefix). Store the geohash, index it like any string, and a radius search becomes a prefix query over the cells covering your area. Simple and works with an ordinary database or Redis geo.
• Quadtree — recursively divide space into four quadrants until each cell holds few points; dense areas (downtown) subdivide more than sparse ones. A query walks down to the relevant cells. Adapts to uneven density.

query: places near (lat, lng) within R
  → compute the geohash cells covering the radius
  → fetch candidate places in those cells  (small set, not the whole table)
  → compute exact distance on candidates, filter to R, sort

The index narrows billions of places to a few candidate cells; you only compute exact distance on that small set.

4. Serving it

Because data is static and read-heavy, this is a Scaling Reads dream:

• Keep the geo index in a fast store — Redis geospatial commands (GEOADD/GEOSEARCH) do radius queries out of the box; Elasticsearch geo_distance combines geo with attribute filters ("Italian AND within 2km AND rating > 4").
• Cache popular query areas; results change rarely so cache TTLs can be long.
• Replicate for query throughput.

5. Combining geo with filters

Real queries are "sushi, open now, within 1km, 4★+." The clean approach is a search engine that indexes both the geo point and the attributes, so one query applies the radius and the filters together, then sorts by distance — rather than geo-filtering and attribute-filtering in two separate passes. This is why Elasticsearch is a common choice here.

6. Deep dives

• Boundary correctness: a naive geohash prefix can miss points just across a cell edge — query the target cell and its neighbours to avoid missing nearby results at boundaries.
• Density skew: downtown has thousands of places per cell, the countryside almost none — quadtrees adapt automatically; with geohash, use variable precision.
• Updates: rare, but a new/closed place is a cheap index update; no firehose like moving vehicles.
• "Open now": store hours and evaluate against the query time — a filter, not part of the geo index.

What to emphasise

Make the geospatial index the whole answer, and note it's read-heavy and static:

"Proximity search can't use a normal B-tree, so I'd index places geospatially — geohash, where nearby points share a string prefix, or a quadtree that adapts to density. A radius search resolves to the handful of cells covering the area, I fetch candidates from those cells plus their neighbours to avoid boundary misses, then compute exact distance only on that small set and sort. The data is static and read-heavy, so I'd serve it from Redis geo or Elasticsearch — the latter lets me combine the radius with attribute filters like 'open now, 4★+' in one query — and cache popular areas with long TTLs."

Next up: Photo Sharing — media upload, storage, and delivery.