Design Yelp (Proximity Location Search & Spatial Indexing)

Proximity search systems allow users to query: *"Find the top-rated Italian restaurants within a 3-mile radius of my current GPS coordinates."* Serving this efficiently requires specialized geospatial indexing structures that turn 2D spatial coordinate searches into lightning-fast range queries.

1. System Requirements

Functional Requirements

1. Search Businesses: Query places by GPS coordinates, radius, category (Restaurants, Bars), and filters (Rating, Price).
2. Business Profiles: View business details, operating hours, photos, and aggregate ratings.
3. Reviews & Ratings: Add reviews and ratings (1–5 stars) with photos.
4. Business Registration & Updates: Business owners can register new locations and edit details.

Non-Functional Requirements

1. Ultra-Fast Search Latency: Geospatial queries should return within $< 100\text{ms}$.
2. High Read Throughput: Search traffic is massive (100,000+ QPS), whereas business location changes are rare (write QPS $< 50$).
3. Boundary Correctness: Avoid missing nearby venues situated across grid boundary seams.

2. Geospatial Indexing Strategies

1. Geohashing

• Hierarchically subdivides the surface of the earth into a 32-character grid (base-32).
• Longer prefixes represent smaller bounding boxes:
• Length 4: $\approx 39\text{ km} \times 19\text{ km}$
• Length 5: $\approx 4.9\text{ km} \times 4.9\text{ km}$
• Length 6: $\approx 1.2\text{ km} \times 0.6\text{ km}$
• Boundary Problem: If a user is 10 meters inside cell 9q8yy, a venue 20 meters away in neighboring cell 9q8yz won't match a prefix search!
• Solution: Always query the user's geohash plus the 8 surrounding neighbor cells.

2. QuadTrees

• An in-memory 2D tree where every node recursively subdivides into 4 quadrants (NW, NE, SW, SE).
• A node splits only when it contains more than $N$ businesses (e.g. 100 venues).
• Dense cities (Manhattan) have deep trees; rural areas have shallow trees, optimizing memory footprint.

3. High-Level Architecture Blueprint

                                  +-----------------------+
                                  |     Mobile Client     |
                                  +-----------+-----------+
                                              |
                                              | GET /search?lat=37.77&lng=-122.41&r=3km
                                              v
                                  +-----------------------+
                                  |     API Gateway       |
                                  +-----------+-----------+
                                              |
                                              v
                                  +-----------------------+
                                  | Proximity Search Svc  |
                                  +-----+-----------+-----+
                                        |           |
             +--------------------------+           +--------------------------+
             | 1. Find Business IDs                 | 2. Hydrate Details
             v                                      v
+------------------------+             +------------------------+
|  Spatial Index Cache   |             |  PostgreSQL / DynamoDB |
|  (Redis GEO / S2 cells)|             |  (Business Profiles DB)|
+------------------------+             +------------------------+

Key Architecture Trade-Offs & Decision Matrix