TLDR – Designing a Geospatial Search Service

Geospatial search (aka proximity search) powers many apps like Google Maps, Tinder, and Uber by helping users find nearby locations. Designing such a system involves balancing efficiency, scalability, and accuracy.

Techniques for Geospatial Search

Bounding Box Optimization

Approximate circular search areas with rectangles to reduce search overhead.

Geohashing

Converts lat/lon into a compact string for fast prefix-based lookup; efficient, but requires checking neighbors to cover edge cases.

Quadtree

A recursive, memory-efficient structure that adapts to data density; more precise but operationally heavier (batch updates, memory rebuilds).

System Architecture

Stateless, horizontally scalable location service using read replicas; a separate write-light service manages POI data.

Data Modeling

Can store geohashes in normalized or denormalized formats; tradeoffs between simplicity, speed, and edit performance.

Next-Level Considerations

Handle moving users, caching hot zones, dynamic radius expansion, or explore alternatives like Google’s S2 Geometry.

This foundational system design pattern applies broadly in ride-sharing, dating apps, navigation, and IoT. Choose tools (Geohash vs. Quadtree) based on accuracy needs, query volume, and update frequency.

Implementation of Proximity Service

How might we go about implementing a proximity service? Given coordinates and a radius, we can find nearby points of interest while maintaining efficiency and scalability.

Bounding Box Approach

One way to simplify circular radius searches is by using a bounding box, a rectangular area that encompasses the circle. The bounding box can speed up the search by narrowing down the relevant geographical area before filtering out points outside the circular radius.

Non-Functional Requirements

  1. Speed: The search service should return nearby points of interest quickly.
  2. Availability: Our architecture should not hinge on a single point of failure.
  3. Scalability: We should accommodate traffic spikes during peak hours.

Point of Interest Management

The term "point of interest" (PoI) refers to any place of relevance to users, such as restaurants and hotels. The management service is tasked with mutating PoI data, acting as a write-only service expecting low request volume.

The Location Service

The location service is read-heavy and expects high request volume. It remains stateless to allow for horizontal scaling, interfaces with a database cluster, and focuses on finding POIs within a radius of the user's position.

Searching for Points of Interest

Traditional Methods

B-trees in relational databases are hierarchical and may lead to full table scans. Although indices on latitude and longitude help, they do not significantly speed up queries because we must intersect two sets of results.

Geohashing Overview

Geohashing encodes latitude and longitude into a single value, facilitating more efficient searches. It subdivides the world recursively into quadrants and can represent locations as compact strings. The precision of geohashing is flexible, ranging from the size of the world to centimeters.

Using Geohashing for Searches

We can store a geohash for each POI. Given the user’s geohash, we can query for nearby points efficiently. We also retrieve points from neighboring geohashes to handle edge cases.

Quadtree as an Option

A quadtree helps represent spatial data hierarchically, where the root represents the entire world. To find locations within a radius, we traverse this tree to the desired leaf node. However, the quadtree's operational implications may favor geohashing as the simpler choice.

Data Modeling

The points_of_interest table should accommodate our geohash structure, either normalized or denormalized.

Request Lifecycle

The following steps outline the lifecycle of a user request for nearby points of interest:

  1. The user approaches a map tile, triggering a request with coordinates and radius.
  2. The load balancer forwards the request to the location service.
  3. The location service transforms the user’s coordinates into a geohash.
  4. The location service queries the geohashes table for POI IDs matching the search criteria.
  5. The geohash service queries the points_of_interest table using these IDs.
  6. Finally, the location service returns the nearby points of interest to be displayed on the map.

Future Considerations

  1. Optimizing searches for moving users
  2. Caching strategies for densely populated areas
  3. Fetching geohash neighbors to handle edge cases
  4. Auto-expanding search radius if needed
  5. Exploring advanced options like Google’s S2 geometry library.

Next Steps in Geospatial Search

Geospatial search is an active research area with applications in geofencing, route planning, mobility prediction, and real-time navigation. This field offers a great entry point for understanding modern location-based services.