Efficient matchmaking: scaling from panic responders to ride-hailing

In our team’s latest project, we’ve built a responder app feature designed to handle user “panics”—urgent scenarios requiring immediate attention, such as medical or security emergencies. The core challenge? Efficiently identifying the nearest responder to the panic location.

This system isn’t just limited to emergency response. Imagine a ride-hailing platform like Uber, where the goal is to match riders with the nearest available driver. At its heart, both applications share the same underlying challenge: efficient spatial matchmaking. In this blog post, we’ll walk you through how we approached and solved this problem, and how the solution can scale across cities and use cases.

The responder

Here’s how our responder app works:

1. Triggering the Panic: A user triggers a panic for either medical or security reasons.
2. Assigning a Controller: The system routes the panic to a designated controller for validation.
3. Finding Nearest Responders: Up to five responders near the panic location are identified.
4. Dispatching Help: If the controller confirms the panic, the most appropriate responder is dispatched.

We're going to focue on step 3: finding the nearest responders to a given location in real-time. Currently, our system operates in Johannesburg but is designed to scale globally.

Using GeoJSON to Represent Geographic Data

GeoJSON is a standard format for encoding geographic data structures like points, polygons, and lines. In our case, we divided Johannesburg into a 4x4 grid, creating 16 square polygons to represent discrete areas of coverage.

Why a Grid?

• Simplifies spatial queries by localizing searches.
• Provides clear boundaries for responders.
• Makes the system scalable and computationally efficient.
• Each grid is represented as a polygon in a GeoJSON file. Here’s an example of a simple polygon in GeoJSON:

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "properties": { "id": 1 },
      "geometry": {
        "type": "Polygon",
        "coordinates": [
          [
            [-74.0, 40.7],
            [-74.0, 40.8],
            [-73.9, 40.8],
            [-73.9, 40.7],
            [-74.0, 40.7]
          ]
        ]
      }
    }
  ]
}

This snippet demonstrates how we store geographic areas as polygons. In our actual implementation, we have a GeoJSON file that covers the entire city with similar features.

Spatial Indexing with STRtree

Storing polygons is only half the battle. Querying them efficiently, especially in real-time, is where the real challenge lies. To achieve this, we use an STRtree, an R-tree implementation in the NetTopologySuite library.

What is an STRtree?

STRtree (Sort-Tile-Recursive R-tree) is a spatial data structure that enables fast querying of geographic features. Instead of checking every polygon for a given point, STRtree allows us to narrow down the search to relevant polygons in logarithmic time.

Steps to Build the STRtree:

1. Load Polygons: Each grid polygon is inserted into the STRtree with its spatial boundaries.
2. Build the Index: Once all polygons are inserted, we build the tree for efficient queries.

By using STRtree, we can quickly determine which grid a given point falls into or identify grids near a specific location.

Finding the Nearest Responders

Let’s walk through the end-to-end workflow for finding the nearest responders to a panic location:

1. Locate the Panic Grid

• Convert the latitude and longitude of the panic location into a point.
• Query the STRtree to find the grid containing this point.
• Handle edge cases where the point falls outside our coverage area gracefully.

2. Check for Responders in the Grid

• Fetch all active responders in the grid.
• Rank responders by their distance to the panic location.

3. Expand the Search if Needed

• If no responders are found in the immediate grid, query the nearest grids using a precomputed lookup table.
• Repeat the process until suitable responders are found or all options are exhausted.

The lookup table of nearest grids is precomputed using centroids and STRtree’s nearest neighbor capabilities. This preprocessing step ensures that searches can expand seamlessly without significant computational overhead.

Code Implementation Highlights

Here are some key components of our implementation:

Loading Grids from GeoJSON

We load the GeoJSON file and convert each polygon into a grid object:

public async Task<List<Grid>> LoadGridsFromGeoJson(string geoJson) {
var geoJsonReader = new GeoJsonReader();
var featureCollection = geoJsonReader.Read<FeatureCollection>(geoJson);

    var grids = featureCollection.Select(feature => new Grid {
        Id = (int)feature.Attributes["id"],
        Boundary = feature.Geometry as Polygon
    }).ToList();

    Add(grids);
    return grids;
}

Querying the STRtree

When a panic occurs, we locate the corresponding grid:

public Grid FindGridForLocation(Point location) {
    var queryEnvelope = new Envelope(location.Coordinate);
    var queryGrids = gridIndex.Query(queryEnvelope);

    return queryGrids.FirstOrDefault(grid => grid.Boundary.Contains(location));
}

Precomputing Nearest Grids

To expand searches efficiently, we preprocess nearest grids:

private void PreprocessNearestGrids(List<Grid> grids, int numberOfNearestGrids = 5) {
    foreach (var grid in grids) {
        var nearestNeighbours = gridIndex.NearestNeighbour(
            grid.Boundary.EnvelopeInternal, grid, new CentroidItemDistance(), numberOfNearestGrids);

        nearestGridsLookup[grid.Id] = nearestNeighbours.Where(g => g != grid).ToList();
    }
}

Scaling and Future Use Cases

Beyond Johannesburg

While this system currently operates in Johannesburg, it’s designed to scale globally. By simply loading a new GeoJSON file for a different city and re-indexing the grids, the same approach can be applied anywhere.

Applications Beyond Emergencies

The matchmaking logic described here is versatile. Some examples include:

• Ride-Hailing: Matching riders with the nearest drivers.
• Delivery Services: Finding the closest delivery personnel to a pickup location.
• Crowdsourced Services: Identifying the nearest taskers for on-demand jobs.

Future Enhancements

1. Dynamic Grids: Adjust grid sizes dynamically based on population density or demand.
2. Advanced Indexing: Explore more sophisticated spatial indexing techniques for larger datasets.
3. Multi-City Support: Implement seamless handling of multiple cities in a single deployment.

Conclusion

By combining GeoJSON, STRtree, and precomputed lookup tables, we’ve built a fast, scalable, and adaptable system for finding the nearest responders to a given location. The same principles can power a wide variety of location-based applications beyond emergency response. As we continue to refine and expand this solution, the possibilities for real-time matchmaking are endless. If you’re building a similar system or exploring spatial computing challenges, we hope this deep dive provides valuable insights!