🧭 Concept H3 & global grids Performance & scale H3 & Global Grids · step 12 of 20 Updated

Geohash Explained: Prefixes, Precision and the Edge Problem

Problem statement

A geohash turns a coordinate into a short string — gcpuvp for central London — with a property that looks like magic: points that share a prefix are in the same cell. That makes proximity look like string matching, which every database, key-value store and search index is good at.

The magic has a limit that most uses of geohash eventually hit. Two points 9 metres apart on either side of the Greenwich meridian encode as gcpuzgrbw and u10hb5209, and share no characters at all.

That is not an exotic corner. Measured on 107,956 distinct GeoNames locations in Great Britain, 22.8% of true nearest neighbours fall in a different precision-5 cell, and at precision 6 the figure is 74.3%. A proximity search that looks only inside one geohash cell misses a large share of the answer, and the loss grows as the cells get finer.

Quick answer

Encode, then search the cell and its eight neighbours, never the cell alone:

import pygeohash as pgh

home = pgh.encode(51.5007, -0.1246, precision=6)       # 'gcpuvp'
north, south = pgh.get_adjacent(home, "top"), pgh.get_adjacent(home, "bottom")
block = [home, north, south,
         pgh.get_adjacent(home, "right"), pgh.get_adjacent(home, "left"),
         pgh.get_adjacent(north, "right"), pgh.get_adjacent(north, "left"),
         pgh.get_adjacent(south, "right"), pgh.get_adjacent(south, "left")]
print(block)

Measured on the British points, a radius search of 500 m at precision 5 found 91.0% of the true neighbours by looking in the home cell, and 100.0% by looking in the 3×3 block.

Table of geohash precision levels 4 to 8 with cell width and height in kilometres.
Odd precisions give square cells at the equator; even precisions give cells twice as wide as they are tall.

Step-by-step solution

1. Bisect longitude and latitude alternately

A geohash is built by repeated halving. The first bit says whether the longitude is in the western or eastern half of −180..180; the second says whether the latitude is in the southern or northern half of −90..90; the third halves the chosen longitude range again, and so on.

The bits interleave, longitude first. After 30 bits the point is known to within a small rectangle, and every earlier bit describes a larger rectangle containing it.

2. Group the bits into base-32 characters

Every five bits become one character from the alphabet 0123456789bcdefghjkmnpqrstuvwxyz (no a, i, l or o). So precision 6 is 30 bits: 15 for longitude, 15 for latitude.

At odd precisions the longitude gets one more bit than the latitude. That is why cell shapes alternate, as the next step's table shows.

3. Know what each precision means on the ground

Computed from the bit counts, with a degree of longitude shrinking by cos(latitude):

precision   width at equator   height      width at 60°
    4          39.092 km       19.546 km     19.546 km
    5           4.887 km        4.887 km      2.443 km
    6           1.222 km        0.611 km      0.611 km
    7           0.153 km        0.153 km      0.076 km
    8           0.038 km        0.019 km      0.019 km

Heights never change with latitude; widths halve by 60°. A precision-6 cell is 1.2 km × 0.6 km at the equator and a square 0.6 km × 0.6 km in Oslo.

4. Read a prefix as containment

gcpuvp is inside gcpuv, which is inside gcpu, and so on. A LIKE 'gcpuv%' query, a prefix scan in a key-value store or a range scan on a sorted string column returns every point inside that cell — exactly, and cheaply.

This is the property worth having. Everything that follows is about what it does not promise.

5. Do not read a shared prefix as nearness

A shared prefix proves two points are in the same cell. A different prefix proves nothing, because nearby points on opposite sides of a cell boundary are in different cells — and at a high-level boundary they differ from the very first character.

Measured among British nearest-neighbour pairs less than 1 km apart, 15.44% share fewer than five characters and 2.79% share fewer than four. Sixty-four pairs share none, with a median separation of 719 m: they straddle the prime meridian, where the first bit flips.

6. Search the 3×3 block

The fix is to add the eight neighbouring cells to every lookup. A neighbour is computed from the cell itself, so crossing the meridian is handled: the eastern neighbour of gcpuzg is u10hb5.

Measured, 2,000 radius searches of 500 m over the British points returned every true neighbour — 0 missed of 6,228 — in 0.02 ms each, against 2.67 ms for a brute-force distance scan.

7. Choose the precision from the search radius

The 3×3 block guarantees completeness only when the radius is no larger than the cell's smaller dimension at the data's highest latitude. For Great Britain, reaching 60.86° north, that is 2.32 km at precision 5.

At precision 6 the same 1 km search found only 92.3% of neighbours even with the 3×3 block, because the cells were smaller than the radius. Too fine is as broken as a single-cell lookup.

Bar chart of the share of nearest neighbours in a different geohash cell at precisions 4 to 8.
The finer the cell, the more neighbours live next door rather than at home.

Code examples

Example 1 — cell size at a latitude 

import math


def geohash_cell_size(precision, lat=0.0):
    """Width and height of a geohash cell in km at a given latitude."""
    lon_bits = math.ceil(5 * precision / 2)
    lat_bits = math.floor(5 * precision / 2)
    km_per_degree = math.pi * 6371.0088 / 180
    width = 360 / 2 ** lon_bits * km_per_degree * math.cos(math.radians(lat))
    height = 180 / 2 ** lat_bits * km_per_degree
    return round(width, 3), round(height, 3)
>>> geohash_cell_size(5), geohash_cell_size(5, 51.5), geohash_cell_size(6, 51.5)
((4.887, 4.887), (3.042, 4.887), (0.76, 0.611))

The bit counts were checked against pygeohash itself: cell indices computed this way agreed with pgh.encode on 40,000 of 40,000 comparisons.

Example 2 — the 3×3 block 

import pygeohash as pgh


def neighbours_3x3(gh):
    """The cell and its eight neighbours, crossing prefix boundaries correctly."""
    north, south = pgh.get_adjacent(gh, "top"), pgh.get_adjacent(gh, "bottom")
    return [gh, north, south, pgh.get_adjacent(gh, "right"), pgh.get_adjacent(gh, "left"),
            pgh.get_adjacent(north, "right"), pgh.get_adjacent(north, "left"),
            pgh.get_adjacent(south, "right"), pgh.get_adjacent(south, "left")]
>>> neighbours_3x3("gcpuvp")
['gcpuvp', 'gcpvj0', 'gcpuvn', 'gcpuvr', 'gcpuuz', 'gcpvj2', 'gcpvhb', 'gcpuvq', 'gcpuuy']
>>> neighbours_3x3("gcpuzg")[:5]
['gcpuzg', 'gcpuzu', 'gcpuzf', 'u10hb5', 'gcpuze']

Note how many of London's neighbours change the fourth or fifth character. In pygeohash 3.5.1, get_adjacent accepts the directions "top", "bottom", "left" and "right".

Example 3 — a radius search that cannot silently miss 

import math
from collections import defaultdict

import numpy as np
import pygeohash as pgh


class GeohashIndex:
    """Radius search over points using geohash buckets plus an exact check."""

    def __init__(self, lats, lngs, precision):
        self.lats = np.asarray(lats, dtype=float)
        self.lngs = np.asarray(lngs, dtype=float)
        self.precision = precision
        self.buckets = defaultdict(list)
        for i, (lat, lng) in enumerate(zip(self.lats, self.lngs)):
            self.buckets[pgh.encode(lat, lng, precision=precision)].append(i)
        width, height = geohash_cell_size(precision, float(np.abs(self.lats).max()))
        self.safe_radius_km = min(width, height)

    def within(self, lat, lng, radius_km):
        if radius_km > self.safe_radius_km:
            raise ValueError(f"radius {radius_km} km exceeds {self.safe_radius_km} km; "
                             f"a 3x3 search at precision {self.precision} could miss points")
        home = pgh.encode(lat, lng, precision=self.precision)
        candidates = np.array([i for cell in neighbours_3x3(home) for i in self.buckets.get(cell, ())], dtype=int)
        if len(candidates) == 0:
            return candidates
        la1, lo1 = math.radians(lat), math.radians(lng)
        la2, lo2 = np.radians(self.lats[candidates]), np.radians(self.lngs[candidates])
        a = np.sin((la2 - la1) / 2) ** 2 + math.cos(la1) * np.cos(la2) * np.sin((lo2 - lo1) / 2) ** 2
        distance = 2 * 6371.0088 * np.arcsin(np.sqrt(a))
        return candidates[distance <= radius_km]
built index over 107,956 points in 0.05s, 19,034 buckets, safe radius 2.322 km
2,000 queries at 500 m: index 0.02 ms each, brute force 2.67 ms each; missed 0 of 6,228
ValueError: radius 5 km exceeds 2.322 km; a 3x3 search at precision 5 could miss points

The guard is the useful part. A geohash search that returns fewer results than it should looks exactly like a correct one, so the class refuses the radii it cannot answer completely.

Explanation

Why a prefix is a cell

Each character appends five bisections. Keeping only the first n characters discards the later bisections and leaves the larger rectangle they subdivided. So truncation is exactly "the containing cell at a coarser precision", with no computation beyond slicing a string.

That makes geohash unusually convenient for systems that only understand strings: one sorted column serves every precision at once.

Why neighbours can share nothing

Sorting cells by their geohash traces a Z-order curve: it sweeps a quadrant completely before moving to the next. Cells that are adjacent across a quadrant boundary are far apart in that order.

The boundary between the first characters g and u is the prime meridian in northern mid-latitudes. Every British location just east of Greenwich starts with u; every one just west starts with g. The geometry is continuous; the string is not.

Why the edge problem gets worse as cells shrink

Whether a point's nearest neighbour is in the same cell depends on the ratio between neighbour distance and cell size. The British points have a median nearest-neighbour distance of 606 m.

A 39 km precision-4 cell holds almost every such pair, and only 4.4% cross a boundary. A 1.2 km precision-6 cell holds a minority of them: 74.3% cross one, and 21.77% of nearest neighbours were not even in the 3×3 block. In a sparser global sample of 2,000,000 points, with a median neighbour distance of 1,742 m, 51.4% already crossed at precision 5.

Why geohash cells are not equal areas

The bisection is in degrees, so a cell is a fixed fraction of longitude and latitude. On the ground, its width shrinks with the cosine of latitude while its height does not, so a precision-5 cell covers half the area in Oslo that it covers at the equator. Counts per geohash cell are therefore not densities, and a heat map built from them grows paler towards the poles for no reason in the data.

Bar chart of radius search recall using the home geohash cell alone versus the three-by-three block.
The block is nine lookups instead of one, and it is still hundreds of times faster than a distance scan.

Edge cases or notes

  • The antimeridian wraps. Measured, the eastern neighbour of xbpbp, at 179.99° east, is 80000, which decodes to −179.98°, so the 3×3 block crosses it correctly.
  • The poles do not. Asking for the northern neighbour of a cell at 89.99° north raised ValueError: No adjacent geohash to the top: it would lie beyond the north pole; catch it if your data reaches polar latitudes.
  • Pygeohash's argument order is encode(latitude, longitude), like H3 and unlike shapely.
  • Even precisions are rectangles twice as wide as tall at the equator; do not assume square cells in distance arithmetic.
  • Exact duplicates always share a cell. Deduplicate coordinates before measuring neighbour statistics, or the edge problem looks smaller than it is.
  • Precision beyond 9 or 10 exceeds the accuracy of most coordinates and only adds characters.
  • A geohash is not unique per cell area — the same string length means very different areas at different latitudes.
  • For hexagonal neighbourhoods or equal-ish areas, H3 or S2 are the better index; geohash's strength is that it is a plain string.

FAQ

What is a geohash?

A base-32 string that encodes a latitude–longitude cell by alternately halving longitude and latitude ranges. Each extra character narrows the cell by five bisections, so a prefix is always the containing cell.

Do points with the same geohash prefix lie close together?

Yes, they are in the same cell. The reverse is false: two points 9 m apart across the Greenwich meridian share no characters at all.

What is the geohash edge problem?

Nearby points on opposite sides of a cell boundary get different hashes. Measured on British locations, 22.8% of nearest neighbours fell in a different precision-5 cell and 74.3% in a different precision-6 cell.

How do I search for nearby points with geohash?

Look up the home cell and its eight neighbours, then filter candidates by exact distance. That found every neighbour within 500 m in a test of 2,000 searches, against 91.0% for the home cell alone.

How big is a geohash cell?

At precision 5, about 4.9 km square at the equator; at precision 6, 1.2 km by 0.6 km. Widths shrink with latitude, so both are narrower in northern Europe.

Should I use geohash or H3?

Geohash when you need a plain string key that any database can prefix-scan. H3 when you need near-equal areas or uniform neighbours for analysis.