Proximity Search (Yelp / Nearby Restaurants)

0) Problem Restatement

Design a service that answers: "show me places near me". Given a user's location (latitude and longitude), a radius, and optional filters or text ("pizza", "open now", rating 4+), return the top K places sorted by a mix of distance and quality. Examples include Yelp, Google Maps nearby, or restaurant search in Uber Eats.

Places change rarely, but searches happen constantly. So this is a read-heavy problem, and the main question is how to find nearby points quickly.

1) Requirements

1.1 Functional

• Search by location + radius (or "nearest K").
• Optional text query and filters (category, price, rating, open now).
• Return ranked results with distance.
• Business owners add and update places (changes can take a few minutes to show).

1.2 Non-Functional

• Low latency: under ~100 ms.
• High read throughput, peaks at meal times.
• Global coverage: very dense cities and empty countryside.

1.3 Scale Estimates

• 200M places worldwide × 1 KB ≈ 200 GB of place data.
• 100M daily users × 5 searches = 500M searches/day ≈ 6K/sec, peak ~30K/sec.
• Writes (new or updated places): a few hundred per second. Tiny in comparison.

1.4 API Design

• GET /v1/search?lat=12.97&lng=77.59&radius=2000&q=pizza&open_now=true&limit=20&cursor=

• GET /v1/places/{id}
• POST /v1/places, PATCH /v1/places/{id} (owners)

2) High-Level Architecture

2.1 Overview

• Search Service: turns the location into a set of map cells, fetches candidates, filters and ranks them.
• Geo index: maps cells to place IDs. It fits in memory on each search server, or lives in a search engine with geo support (Elasticsearch/OpenSearch geo queries).
• Place DB: full place details (SQL or document store), fronted by a cache.
• Indexer: listens to place changes and updates the index.

2.2 Architecture Diagram

flowchart LR
    U["User app"] --> LB["Load balancer"]
    LB --> SS["Search Service"]
    SS --> GI[("Geo + text index - replicated")]
    SS --> C[("Place details cache")]
    C --> DB[("Places DB")]
    O["Business owners"] --> PS["Place Service"]
    PS --> DB
    PS --> K[("Change events")]
    K --> IX["Indexer"]
    IX --> GI

3) How to Find Nearby Points

Scanning 200M places for each query is impossible, so we split the map into cells.

1. Compute the user's geohash at a precision where cells are about the size of the radius.
2. Take that cell plus its 8 neighbors. A place just across a cell border can be closer than one inside the same cell.
3. Get all places in those 9 cells, compute the exact distance, and keep those within the radius.

Google's S2 and Uber's H3 are cell systems with similar ideas and better shapes. Any of these is fine in an interview if you explain the neighbor-cell trick.

4) Key Flows

4.1 Search

1. Compute the covering cells for the circle.
2. Get candidate place IDs from the index for those cells, applying filters there if possible (category, open now).
3. For text queries, intersect with a text match (an inverted index on names, categories and dishes).
4. Rank: score = w1 × relevance + w2 × rating + w3 × popularity − w4 × distance.
5. Fetch details for the top 20 from the cache and return them with a cursor for the next page.

4.2 Updating a place

The owner edits hours or a location → Place DB → change event → indexer updates the cell entry. A delay of a minute or two is acceptable.

5) Deep Dive A — Dense cities and sparse areas

• If a small radius in Manhattan returns 5,000 places, cap the candidates per cell and rely on ranking.
• If a 2 km radius in the countryside returns nothing, expand the search to larger cells until we have enough results (or show "nearest K" instead).
• Quadtrees and adaptive cell sizes handle both cases naturally.

6) Deep Dive B — Scaling and caching

• The geo index for 200M places (ID + cell + a few filter fields ≈ 50 bytes) is ~10 GB, which fits in memory. Replicate it on many search servers to scale reads.
• For even more scale, shard by region (e.g., by country or large geohash prefix). Queries near a border ask two shards.
• Cache popular queries by (rounded location cell + query + filters) for a few minutes. Lunchtime "pizza near downtown" repeats a lot.
• For a delivery app, also filter by "does this restaurant deliver to this address" and rank by estimated delivery time. These need live data (courier supply, kitchen load), which comes from a fast store.

7) Trade-offs & Alternatives

8) Common Follow-up Questions

• "Why not just use SQL with latitude/longitude ranges?" A bounding-box query on two columns can't use one index efficiently at this scale. Geo cells turn it into a simple key lookup.
• "Moving objects like drivers?" That's different: locations change every few seconds, so keep them in an in-memory geo index updated from a stream (see the ride-hailing design).
• "Personalization?" Add user features (cuisines you order, price level) to the ranking step.

9) Wrap-Up

Split the map into cells (geohash, quadtree, S2 or H3), search the user's cell plus its neighbors, then filter by exact distance. Combine with text search and filters, rank by relevance, rating and distance, and fetch details from a cache. Replicate the in-memory index for reads, shard by region at global scale, and expand the search area where places are sparse.