How GeoHash Enables Efficient Nearby Passenger Search in Ride-Hailing Apps

Background: The Nearby Search Problem

Ride-hailing services like Didi need to quickly find passengers within a certain radius (e.g., 1 km) of a driver. A naive approach stores every user's (longitude, latitude) pair in an array and computes distances to all entries on each query. However, with massive data volumes, full traversal becomes computationally infeasible.

GeoHash Basic Principle

GeoHash converts a 2D coordinate into a 1D string through two steps:

Recursive bisection of longitude and latitude ranges to produce binary strings.

Base32 encoding of the interleaved binary string for compact storage.

Longitude Bisection Example

For longitude 116.3111126 (range -180 to 180), each step compares the value to the midpoint and outputs 1 if greater, 0 otherwise, narrowing the interval:

bit | left      | mid       | right
1   | -180      | 0         | 180
1   | 0         | 90        | 180
0   | 90        | 135       | 180
1   | 90        | 112.5     | 135
0   | 112.5     | 123.75    | 135
0   | 112.5     | 118.125   | 123.75
1   | 112.5     | 115.3125  | 118.125
0   | 115.3125  | 116.71875 | 118.125
1   | 115.3125  | 116.015625| 116.71875
0   | 116.015625| 116.3671875|116.71875
1   | 116.015625| 116.19140625|116.3671875
1   | 116.19140625|116.279296875|116.3671875
0   | 116.279296875|116.323242188|116.3671875
1   | 116.279296875|116.301269532|116.323242188
0   | 116.301269532|116.31225586|116.323242188
Result: 110100101011010 (15 bits)

Latitude Bisection Example

For latitude 40.085003 (range -90 to 90):

bit | left      | mid       | right
1   | -90       | 0         | 90
0   | 0         | 45        | 90
1   | 0         | 22.5      | 45
1   | 22.5      | 33.75     | 45
1   | 33.75     | 39.375    | 45
0   | 39.375    | 42.1876   | 45
0   | 39.375    | 40.78125  | 42.1876
1   | 39.375    | 40.078125 | 40.78125
0   | 40.078125 | 40.4296875| 40.78125
0   | 40.078125 | 40.25390625|40.4296875
0   | 40.078125 | 40.166015625|40.25390625
0   | 40.078125 | 40.1220703125|40.166015625
0   | 40.078125 | 40.1000976563|40.1220703125
0   | 40.078125 | 40.0891113282|40.1000976563
1   | 40.078125 | 40.0836181641|40.0891113282
Result: 101110010000001 (15 bits)

Interleaving and Base32 Encoding

The 15-bit longitude and 15-bit latitude strings are interleaved (longitude bit first, then latitude bit) to form a 30-bit string: 11100 11101 00100 11000 10100 01001 This 30-bit string is split into six 5-bit groups (each representing 0–31). Each group indexes into a 32-character alphabet (0-9, A-Z excluding some letters) to produce a 6-character Base32 code. The author notes that the number of bisection steps (bit length) is a trade-off: more bits yield higher precision but require more computation.

Applying GeoHash to Nearby Passenger Search

Because nearby coordinates share longer common prefixes in their GeoHash strings, a prefix match can quickly narrow down candidates. For example, all users whose GeoHash starts with the same 5-character prefix lie in the same rectangular grid cell. The system only needs to compare distances within that cell (and possibly adjacent cells) instead of scanning all users.

Remaining Challenge: Edge Cases

A single Base32 cell covers an area, not a point. Two points in adjacent cells may be closer than two points in the same cell. The article illustrates a case where user A and B share a prefix (suggesting proximity), but A is actually closer to E, C, or D which fall in neighboring cells.

This edge problem requires additional logic (e.g., checking neighboring cells) which the author plans to cover in a follow-up.