↑ back

geohash notes

algorithms gis study-notes

a geohash identifies a rectangular area around a fixed point, and the length of the hash sets the precision. long shared prefix ⇒ spatially close; chop characters off the end ⇒ gradually coarser cell. that asymmetry is the whole design: prefix similarity is a sufficient signal for proximity, never a guarantee - two points on opposite sides of a cell boundary (or the 180° meridian, or a pole) can be 10 m apart with wildly different codes.

my source note collected an unsourced “who uses geohash” list (Yelp, Google Maps, Uber, Airbnb) - dropped. the mechanics below are all that survived the port, plus a re-derived worked example.

POI search via geohash

the proximity trick behind every “nearby” tab:

  • get the user’s lat/lon
  • compute their geohash
  • choose the precision: longer prefix = tighter cell = fewer, closer results; truncate the other way for wider search
  • match prefix against the indexed POIs (all indexed by geohash prefix)
  • tune the length until the candidate count is sane (you always re-filter by true distance afterwards - prefix match only proves which cell, not distance)

the algorithm

bisect the planet. maintain a bounding box for latitude (-90, 90) and longitude (-180, 180). pick the target’s midpoint; whichever half it falls in, record 1 and narrow the box to that half, else record 0. alternate between longitude and latitude with every bit (longitude first), reading binary digits MSB-first (16, 8, 4, 2, 1). every 5 bits → one base32 character → one grid cell. shorter string = fewer bits = bigger cells = lower precision.

the base32 alphabet is 0123456789bcdefghjkmnpqrstuvwxyz - digits 0-9 plus 22 lowercase letters, with a, i, l, o excluded to cut transcription errors (correction of the folklore i’d written down earlier: it’s not “excluding vowels” - i/l/o yes, but also a, while e and u stay).

the worked example, recomputed

the example that floats around (“latitude 37.7749° N, longitude 122.4194° W → geohash w15df6577r2tsllft4”) is wrong twice over: it treats west longitude as positive, and its interleaved bit string doesn’t decode to anything. here is the correct walkthrough, computed with the algorithm above.

location: latitude 37.7749, longitude -122.4194 (west is negative!).

bisect longitude/latitude alternately, 40 bits (longitude gets the even bits):

  • interleaved: 0100110110010001111011110100100100011110
  • take 5 bits at a time and look up base32:
bits value char
01001 9 9
10110 22 q
01000 8 8
11110 30 y
11110 30 y
10010 18 k
01000 8 8
11110 30 y

geohash: 9q8yyk8y (the well-known san francisco prefix 9q8yy falls out of the first 20 bits - a good sanity check).

precision → cell size

computed cell dimensions (km, lon side scaled by cos(latitude), shown at 37.77°):

chars lon bits / lat bits cell size
1 2 / 3 ~7900 × 2500 km
2 5 / 5 ~990 × 625 km
3 7 / 8 ~250 × 78 km
4 10 / 10 ~31 × 20 km
5 12 / 13 ~7.7 × 2.4 km
6 15 / 15 ~970 m × 610 m (≈0.6 km²)
7 17 / 18 ~240 × 76 m
8 20 / 20 ~30 × 19 m

note the pattern: 5 bits per char alternate lon/lat starting with lon, so odd precisions give latitude one extra bit (bigger cells straddle the globe’s east-west extent asymmetrically).

implementation

an older draft i had lying around was broken in four ways at once (encode used 5 longitude bits then 5 latitude bits per character instead of alternating; decode was indented outside the class; self.__base32 referenced a name-mangled attribute that didn’t exist; the alphabet constant lived at module bottom in a way that wouldn’t import). this is the corrected version, verified against the worked example above:

class GeoHash:
    base32 = '0123456789bcdefghjkmnpqrstuvwxyz'

    def __init__(self, latitude, longitude, precision=12):
        self.latitude, self.longitude, self.precision = latitude, longitude, precision

    def encode(self):
        lat_lo, lat_hi, lon_lo, lon_hi = -90.0, 90.0, -180.0, 180.0
        bits = [16, 8, 4, 2, 1]
        chars, ch, bit, even = [], 0, 0, True
        while len(chars) < self.precision:
            mid = (lon_lo + lon_hi) / 2 if even else (lat_lo + lat_hi) / 2
            value = self.longitude if even else self.latitude
            if value >= mid:
                ch |= bits[bit]
                if even: lon_lo = mid
                else: lat_lo = mid
            else:
                if even: lon_hi = mid
                else: lat_hi = mid
            even = not even
            if bit < 4:
                bit += 1
            else:
                chars.append(GeoHash.base32[ch])
                ch, bit = 0, 0
        return ''.join(chars)

    @classmethod
    def decode(cls, geohash):
        lat_lo, lat_hi, lon_lo, lon_hi, even = -90.0, 90.0, -180.0, 180.0, True
        for c in geohash:
            cd = cls.base32.index(c)
            for j in range(5):
                mask = 1 << (4 - j)
                if even:
                    if cd & mask: lon_lo = (lon_lo + lon_hi) / 2
                    else: lon_hi = (lon_lo + lon_hi) / 2
                else:
                    if cd & mask: lat_lo = (lat_lo + lat_hi) / 2
                    else: lat_hi = (lat_lo + lat_hi) / 2
                even = not even
        return (lat_lo + lat_hi) / 2, (lon_lo + lon_hi) / 2

edge cases

  • antimeridian: two points a meter apart on opposite sides of ±180° get hashes with no shared prefix.
  • poles: latitude collapses near ±90°, longitude becomes meaningless - hashes for neighbors diverge.
  • bounded-box search: computing the southwest/northeast corner hashes and scanning everything between retrieves all points along the z-order curve between those corners, which can be orders of magnitude too many (and still breaks at the meridian/poles). production systems keep a filter list of the nearby cells’ prefixes (solr-style) instead of a numeric range scan.

papers & sources

todos

  • neighbor cells (geohash n/s/e/w neighbor calculation for a given hash) - the missing piece for doing real proximity searches without range scans.
  • geohash vs. other space-filling curves (H3, S2) - when the hierarchical-prefix trick stops beating a proper tiling.
  • cross-link a note when i write about z-order curves properly.