How GeoHash Powers Real‑Time Ride‑Hailing: From Theory to Practice

Problem Overview

When a passenger opens a ride‑hailing app, the backend must find drivers within a few hundred meters. Storing every driver’s latitude‑longitude pair in a flat array and scanning the whole list (computing Euclidean or haversine distance for each) works for tiny fleets but becomes infeasible at millions of drivers because of O(N) time and high memory usage.

GeoHash Fundamentals

GeoHash encodes a geographic coordinate into a short string. The algorithm repeatedly bisects the longitude range (‑180 ° to 180 °) and the latitude range (‑90 ° to 90 °). Each bisection yields a binary digit: 1 if the coordinate is greater than the midpoint, otherwise 0. The latitude and longitude bit streams are interleaved (lon‑bit, lat‑bit, …) to form a single binary sequence. The binary sequence is split into 5‑bit groups and each group is mapped to a character from a custom base‑32 alphabet (e.g., “0123456789bcdefghjkmnpqrstuvwxyz”). The resulting string represents a rectangular cell; longer strings correspond to smaller cells (higher precision).

Example (lng = 116.3111126, lat = 40.085003):

Longitude bits (15): 110100101011010
Latitude bits  (15): 101110010000001
Interleaved (30): 111001110100100011000101001
Base‑32 groups → ezs42e44 (illustrative)

Using GeoHash for Driver Proximity

Nearby points share a longer common prefix in their GeoHash strings. To locate drivers near a passenger:

Compute the passenger’s GeoHash to the desired precision (e.g., 6 characters ≈ 1 km, 8 characters ≈ 150 m).

Query the driver store for all records whose GeoHash begins with that prefix.

The query reduces the candidate set from millions to a few dozen.

Optionally perform a precise distance calculation (haversine) on the filtered candidates to enforce the exact radius.

In practice the driver data can be kept in a key‑value store (Redis, Cassandra, etc.) where the GeoHash is the primary key or an indexed column, enabling O(log N) or O(1) prefix look‑ups.

Edge Cases and Mitigations

GeoHash cells are rectangular, so a point near a cell border may have a different prefix from a neighbor that is physically closer, while points inside the same cell can be farther apart than points in adjacent cells. This can cause false negatives or false positives when the search radius is comparable to the cell size.

Dynamic prefix length: Choose a shorter prefix (larger cell) when the requested radius exceeds the cell size, and a longer prefix for tighter searches.

Neighbour cell expansion: Retrieve drivers from the target prefix plus the eight adjacent cells to cover border effects.

Secondary distance filter: After the prefix query, compute the exact haversine distance for each candidate and keep only those within the required radius.

Implementation Sketch (Pseudo‑code)

# Compute GeoHash of passenger location
passenger_hash = geohash.encode(lng, lat, precision=8)

# Determine neighbour hashes (optional)
neighbour_hashes = geohash.neighbours(passenger_hash)

# Query driver store (example with Redis sorted set)
candidates = []
for h in [passenger_hash] + neighbour_hashes:
    candidates.extend(redis.zrangebyscore('drivers:' + h, 0, '+inf'))

# Precise filter
result = []
for driver_id in candidates:
    d_lng, d_lat = get_driver_location(driver_id)
    if haversine(lng, lat, d_lng, d_lat) <= RADIUS:
        result.append(driver_id)