Geohash Rollup: a base-32 address for the map, that nests and has neighbours

The data in this project is synthetic — geolocated points generated locally by data/make_data.py, no OpenStreetMap or gazetteer download. That is deliberate: grading needs the known-correct cell for every point and the exact set of points near each one, which real place data doesn’t come labelled with — and it keeps the project download-free. No signup, no GPU.

Before you start

New to geohashes? Start here.

A geohash is a short text code — like 9q8gr1 — that names a small rectangle on the Earth’s surface. It’s built by repeatedly cutting the world in half: is the point east or west of the prime meridian? North or south of the equator? Each yes/no is one bit; the bits from longitude and latitude are interleaved and packed five at a time into base-32 characters (0-9, b-z minus a,i,l,o). More characters = a smaller, more precise box.

Two properties make this useful, and they are the whole project:

It nests. Chop characters off the end and you zoom out to a bigger box that exactly contains the smaller ones. 9q8gr1 sits inside 9q8g sits inside 9q. So you can aggregate once at fine resolution and get any coarser rollup for free by slicing the string.
Nearby usually share a prefix — but not always. Two points a few metres apart normally get almost the same code. The exception is the catch: if they straddle a cell boundary, their codes differ completely. Proximity done right has to look at a cell and its 8 neighbours.

Part A builds the encoder and the nesting rollup. Part B uses the cells for proximity — and runs straight into the boundary effect. What you’ll learn is in Section 3.

New to Python too? See Start Here — it starts from zero, and shows how to run this in your browser with nothing to install.

1. The Brief

You have a pile of geolocated points and two jobs every mapping stack eventually needs. First, roll them up into a grid — count and sum per cell to find hotspots — at whatever zoom level you ask for, without re-binning. Geohashes give you that: aggregate once at high precision, then truncate the key to zoom out, because the cells nest perfectly. (Rounding lat/lon to N decimals looks like the same idea and isn’t — those bins change real-world size with latitude and don’t nest cleanly.)

Second, find what’s near what — for each point, which other points are within about a cell’s reach. The tempting shortcut is “same geohash = near,” and it’s wrong for most points: two points 30 metres apart routinely land in different cells because a boundary runs between them. The fix is the geohash neighbour operation — decode the cell, step to the 8 adjacent cells, and union them. Geohash indexing underlies proximity search, tile aggregation, and geo-sharding in real systems (Elasticsearch, Redis, and many “points near me” features use exactly this).

2. Difficulty & time

Difficulty 5 / 10. One language, no heavy libraries — but you implement a real algorithm twice: the base-32 encoder (bit-interleaving) in Part A, and the neighbour-cell computation (decode the box, step, re-encode) in Part B. That second mechanic is what lifts it above a one-method project. Calibrated against the ledger (G10): a peer of analytics-with-duckdb (5), polars-analytics (5), and bullwhip-effect (5) — each “implement/operate a genuine technique, not just call one.” Above nearest-facility (4) and spatial-join (3), where a single library call or formula does the work; below warehouse-sim (6), which adds a whole simulation paradigm.

Time is separate from difficulty: Part A is about an hour; Part B is 2–3 hours. The scripts run in under a second.

3. What you’ll be able to do after

Encode lat/lon to a geohash yourself and explain the bit-interleaving — not just import one.
Roll aggregates up and down resolutions by prefix truncation, and prove the cells nest (a coarse cell’s total equals the sum of its children).
Say why rounded-degree bins are not a grid — their real-world size changes with latitude.
Do proximity correctly — union a cell with its 8 neighbours, and show how “same cell only” silently misses points just across a boundary.

The finished result

By the end of Part A you’ll have turned 4,000 raw lat/lon points into a nesting spatial grid — a geohash per point, a rollup per cell, and the proof that the cells nest:

3,529 distinct level-6 cells over 4,000 points        (one geohash code per point)
rolled up per cell:  total value 200,864;  busiest cell 9q8zdy = 269
gh6[:4]  ==  encoding directly at precision 4 for every point   ->  True
level-4 cell total  ==  sum of its level-6 children             ->  True
the rounded-degree trap:  a 0.01° bin is 1.11 km wide at 0°N, 0.89 at 37°N, 0.56 at 60°N

Aggregate once at precision 6 and every coarser rollup is a string slice away — because geohash cells nest exactly, which rounded-degree bins never do.

4. Prereqs & time box

You can write a function, use a loop and a dict, and read a CSV with pandas. No geospatial background needed — Part A hands you the encoding rule step by step. The bit operations (|, and a small lookup table) are explained inline; you don’t need to have seen them before.

Where to write and run code

Two ways to run this project — pick either:

In your browser (no install). If the project page shows a ▶ Run button, click it to run Part A right here — nothing to set up. Part A uses only pandas and numpy, which run in the browser.
On your computer. The one-time setup — installing Python, downloading the code from the course site (no GitHub, no git), opening a terminal, creating a virtual environment, installing the requirements, and running Part A step by step — is covered once in Start Here. Come back here once python -c "import pandas" runs without error. Part B (writing your own solution) needs this local setup.

Time box

Part A — Guided Build: 60–90 minutes. Hard cap.
Part B — Your Turn: 2–4 hours. Hard cap.

5. Setup & data

The data is synthetic and generated locally — see the banner above and SOURCES.md for full provenance. One command creates both parts’ data:

python data/make_data.py

That writes two CSVs into data/ (git-ignored; regenerate anytime, byte-for-byte identical because the seeds are fixed):

Part A — points_a.csv (4,000 rows: point_id, lat, lon, value). The value is what you roll up per cell.
Part B — points_b.csv (3,000 rows: point_id, lat, lon).

Coordinates are uniform lat/lon over a ~1° metro box around 37–38°N, 122–123°W. The geography is generic — the numbers describe no real place; the technique is the point.

6. Part A — Guided Build

You’ll write a geohash encoder, roll a value up per cell, coarsen by truncating the string, and see why rounded degrees don’t behave like a grid. Run the whole thing, or (better) one # %% cell at a time — see Start Here:

python part_a/rollup.py

Prefer the browser? If this page has a ▶ Run button, click it instead of the command above — Part A runs in your browser with nothing to install. The STEP output and every checkpoint below are identical either way.

The full, commented script is in part_a/rollup.py. The spine:

Step 1 — Encode every point to a geohash (precision 6).

Checkpoint: each point gets a 6-character code; here, 3,529 distinct level-6 cells over the 4,000 points. Points in the same cell share the code.

Step 2 — Roll up an aggregate per cell.

Checkpoint: a group-by whose key is a spatial cell — a heatmap in a table. Total value 200,864 across the cells; the busiest cell tops the list.

Step 3 — Coarsen by truncating the prefix; the cells nest.

Checkpoint: truncating a level-6 code to 4 chars equals encoding directly at precision 4 for every point (True), and a level-4 cell’s total equals the sum of its level-6 children (True). Rollups are free: aggregate once, slice the key to zoom out.

Step 4 — Why not just round lat/lon?

Checkpoint: a 0.01° bin is 1.11 km wide at the equator, 0.89 km at 37°N, and 0.56 km at 60°N — same code, different real size. Geohash cells stay in a consistent size class and nest cleanly; rounded-degree bins do neither. Writes part_a/rollup_a.csv.

Why this and not that

Why implement the encoder. Seeing the longitude/latitude bits interleave is what makes the nesting and neighbour behaviour obvious later — a black-box import geohash hides exactly the structure Part B needs.
Why truncation = zoom-out. Because each character adds bits that subdivide the parent box, chopping characters returns you to the parent exactly. That’s why a coarse total is the sum of its children — no re-binning, no double counting.
Why not rounded degrees. A degree of longitude shrinks toward the poles, so equal-degree bins are unequal on the ground and their edges don’t line up across resolutions. Geohash fixes both.

Functions you’ll meet (and where to read more)

Function	What it does here	Docs
bitwise `\|` and a lookup table	Pack 5 bits into one base-32 char	bitwise ops
`str.str[:4]` (pandas)	Truncate the code = zoom out one+ levels	Series.str
`df.groupby(key)["value"].agg`	Roll up count/sum per cell	groupby
`math.cos(math.radians(lat))`	Longitude-km shrink factor by latitude	math

If something looks off

My Part B score is stuck around 0.26 (and pytest fails) — did I do something wrong? No — that is the same-cell-only rule the starter ships with, and it is meant to fail. Two points a few metres apart often land in different cells because a boundary runs between them, so looking at one cell misses about 74% of near neighbours. Union each cell with its 8 neighbours and the set accuracy jumps to 1.00; a red pytest result on the unmodified starter is the exercise, not a bug you caused.
A checkpoint number doesn’t match. The data is seeded, so the numbers are exact. Re-run python data/make_data.py (you may have skipped or edited it), then re-run Part A.
Setup problems (Python not found, pip, FileNotFoundError, re-activating the venv): see the troubleshooting list in Start Here.

7. Part B — Your Turn

Part B is the optional “your turn” half — a guided fill-in-the-blank, not a blank page. You get a working starter (part_b/starter.py) that already handles the easy version; your job is to finish the # TODO it marks out. More open than Part A’s step-by-step, but you are never staring at an empty file. If you finished Part A and want to prove the skill, this is where it happens. New to Python? It’s completely fine to stop after Part A and come back later.

Same core skill — geohash cells — but now for proximity. For every point in points_b.csv, list its co-located points: those in its geohash cell and the 8 adjacent cells at the proximity precision (6). You’re given the encoder plus a neighbors() helper to build on — see part_b/geohash.py.

The transfer: Part A only ever aggregated within the prefix hierarchy — it never needed a cell’s neighbours. Proximity does, because of the boundary effect. In this data 74% of points have a genuinely co-located neighbour that sits in a different cell. The starter looks at the same cell only; it scores 0.26 (779 of 3,000 right) and fails — and the 74% it gets wrong are exactly the points with a boundary neighbour.

Reference rule (reproduce it to match the yardstick)

For each point: encode it at precision 6, take the set of the 9 cells neighbors(code) returns (the cell itself + its 8 neighbours), and collect every other point whose precision-6 code is one of those 9. That set — sorted point ids — is the co-located set. (neighbors() handles the base-32 edge cases for you; you decide when to use it.)

Acceptance criteria (checkable)

Your solution writes into part_b/out/:

colocated.csv — columns point_id, colocated, where colocated is the sorted ids joined by | (empty string if none).
report.json — with keys points, achieved_metric (you can leave achieved_metric null; the grader scores you).

Then:

python part_b/starter.py
pytest part_b/test_solution.py -q

If pytest reports everything as skipped, it just means the output files don’t exist yet — run python part_b/starter.py first (once your solution fills in the TODOs), then re-run.

You’re done when the tests pass. The score is the fraction of points whose co-located set exactly matches the truth, and you need ≥ 0.90 (the reference reaches 1.00). Same-cell-only scores ~0.26.

Constraints — what must be true of your solution, not how to get there

A point’s co-located set must include points from its cell and all 8 neighbouring cells at precision 6.
A point is never co-located with itself; ids in each set are sorted.
Every point in points_b.csv appears once in colocated.csv.
Use the geohash code for the lookup (don’t fall back to raw great-circle distance — the exercise is the cell-and-neighbours query).

Hints

Hint 1 — why same-cell fails

Two points 30 m apart can have completely different level-6 codes if a cell edge runs between them. Same-cell-only can never see across that edge, so it misses one of the two — which is why ~74% of points come out wrong.

Hint 2 — the neighbour block

neighbors(code) returns the 9 codes (the cell + its 8 around it). Bucket every point by its level-6 code first (a dict of code → list of point indices); then for each point, union the buckets for all 9 codes in its block, and drop itself.

Hint 3 — keep it O(n), not O(n²)

Don’t compare every point to every other point. Build the code→points bucket once, then each point only reads its own 9 buckets. That’s why geohash indexing scales.

8. Self-check

You don’t need the answer key. You’re done when all of these hold:

pytest passes — set accuracy ≥ 0.90 (the reference is 1.00).
Turning the 8 neighbours off drops you to ~0.26; turning them on clears the floor. If toggling the neighbours doesn’t move your score, you’re not actually using them.
Re-running from python data/make_data.py reproduces the same numbers — the data is seeded.

And the tell-tale: pick any point whose two nearest others have different codes. Same-cell-only returns an incomplete set for it; the neighbour block returns the full one. If your output matches same-cell-only on that point, you haven’t unioned the neighbours.

9. Stretch

Precision sweep. Redo Part B at precision 5 and 7. Coarser cells catch more per cell (fewer boundary misses) but return farther points; finer cells are tighter but the boundary effect bites harder. Plot accuracy-of-same-cell-only vs precision to see the trade-off.
True radius, not cell block. The 3×3 block is a square approximation of “near.” Add a real haversine filter inside the block to get everything within exactly R metres, and compare.
(Genuinely hard) Adjacent-precision neighbours. Handle a query where the point sits so close to a corner that you need the neighbours of the neighbours — generalise neighbors() to a k-ring and measure how coverage improves.

10. Ship it

Put this in a portfolio repo and it counts. In that repo’s README:

State the finding in one sentence: “same-geohash-means-near misses 74% of truly co-located points because they straddle a cell boundary; unioning the 8 neighbour cells fixes it (0.26 → 1.00 set accuracy).”
Show the nesting proof (coarse total = sum of children) and the boundary-effect number.
Include your encoder and the neighbour query, with one paragraph on why rounded degrees aren’t a grid. That paragraph signals you understand spatial indexing, not just groupby.

Keep make_data.py and the tests in the repo so anyone can reproduce your numbers from zero.

11. Sources

Rendered from SOURCES.md.

Field	Value
Dataset	Synthetic geolocated points (Part A 4,000 with `value`; Part B 3,000) over ~37–38°N, 122–123°W
Type	Synthetic
Generated by	`data/make_data.py` (this repo), seeds `20260746` (A) and `20260747` (B)
Source URL	Not applicable — generated, not fetched
License	Not applicable — synthetic, no third-party rights
Access / generation date	2026-07-18
Redistribution	Permitted — synthetic; output regenerated from the seeded script, never committed
robots.txt checked	Not applicable — no scraping
ToS URL	Not applicable — no external source

Synthetic data teaches the mechanic; it does not prove a finding about the real world. The points were generated on purpose — the geohash indexing techniques are the point, not a claim about any real place.

Next up

Finished this one? Continue the Geospatial track:

Spatial Clusters: finding hotspots with DBSCAN, and why k-means can’t → · Browse all courses