Yelp (Proximity / Location-Based Service)

Mental Model

Proximity services (like Yelp or Google Maps) must resolve query coordinates (latitude, longitude) to nearby points of interest (POIs) under high concurrency and low latency.

A naïve distance query can require a full table scan ($O(N)$) when no spatial index is available. Production systems use spatial indexes or coordinate partitions to narrow candidates, then verify exact distance and radius. Geohashing and QuadTrees are different partitioning strategies; neither promises a universal $O(\log N)$ query because result count, neighbor-cell coverage, density, and index maintenance affect the work.

graph TD
    Client[User Client] -->|1. coordinates| GW[API Gateway]
    GW -->|2. Check Cache| Cache[(Redis Cache)]
    GW -->|3. Query Index| QT[QuadTree Index Service]
    QT -->|4. Find Cells & Neighbors| Map[Geospatial Index Console]
    GW -->|5. Fetch Metadata| MetaDB[(Business Metadata DB)]
    GW -->|6. Sync Updates| GIS[(Geospatial DB PostGIS)]
    GIS -.->|7. Update Index| QT

---

Components and Why They Exist

User Client

Represents the user’s mobile app or web browser requesting nearby businesses. Sends coordinates (lat, lng) and optional search criteria (e.g., category, radius) to the system. In the demo, observe the search circle and pins rendering on the map display.

API Gateway

Serves as the single entry point to route incoming client traffic. Handles rate-limiting, performs auth, parses query coordinates, inspects the Cache Cluster, and routes index and metadata requests. In the demo, notice how request lines emerge from the gateway to the cache and backend services in Steps 5, 6, and 7.

Geospatial DB (PostGIS)

Acts as the durable, transactional database of record for all business locations. Stores geographical columns using spatial extensions (like PostGIS) and persists new restaurant registration updates. In the demo, you can see Step 8 where a new registration inserts coordinates into the PostGIS database before syncing.

QuadTree Index Service

Maintains the in-memory spatial index structure for sub-millisecond search execution. Translates latitude/longitude queries into QuadTree nodes, traverses leaf cells, and resolves nearby business IDs. In the demo, notice the index service highlighting the targeted quadrant and sibling quadrants during Step 5.

Cache Cluster (Redis)

Offloads heavy spatial index lookups for popular coordinate zones. Maps geohash cell prefixes to pre-fetched ranked lists of business IDs. In the demo, watch Step 7 where a request achieves a rapid cache hit and returns to the client immediately.

Business Metadata DB

Stores high-volume, non-geospatial attributes for businesses (e.g., reviews, ratings, hours, images). Serves fast key-value lookups for business profiles once the spatial index identifies candidate IDs. In the demo, observe how spatial candidates are merged with metadata ratings to produce a ranked list in Step 6.

Geospatial Index Console

Displays the visual projection of the geographical map coordinate partition. Renders the hierarchical grid cells (NW, NE, SW, SE) and traces tree traversal and leaf splits. In the demo, watch the grid split into four nested quadrants in Step 3 and Step 8 when business density limits are exceeded.

---

Edge Cases and Misconceptions

The 8-Neighbor Edge Case

If a user is standing on the boundary of geohash cell u, the closest restaurant might be located just 10 meters away in the adjacent cell v. If the index service only queries the user’s primary cell u, it will miss this restaurant. The system must query the user’s primary cell plus all 8 adjacent neighboring cells to guarantee boundary correctness.

Dynamic Tree Rebalancing

While reads are fast on QuadTrees, writing a new business that exceeds a cell’s threshold triggers a quadrant split. Because QuadTrees live in memory, splitting a leaf node requires write locks on the tree. High-frequency registration updates can block reads. Systems solve this by separating the read path (QuadTree servers) and write path (PostGIS DB) and applying index updates asynchronously.

Grid Precision and Geohash Length

Geohash strings vary in length (1 to 12 characters). Each character represents a zoom level. For example, a 6-character geohash represents an area of ~1.2km x 0.6km. Choosing the wrong prefix length can either cache too large an area (returning irrelevant results) or too small an area (causing excessive cache misses). A proximity service must choose cell precision and neighbor coverage based on query radius, then apply exact distance filtering before returning results.