Geocoding Without Google

Background

At Grubhub the address is the first thing the platform learns about an order and the thing the most other systems depend on. A diner types "233 s wacker" into a phone; before anything else can happen that has to become a coordinate accurate enough to pick the right merchants, compute a real drive time, decide whether the address is even inside a delivery boundary, and eventually put a courier at the right door. Every one of those systems has an error budget, and all of them inherit whatever error the geocoder introduced first.

Geocoding looks like string matching until you try it. The input is unconstrained free text typed on a phone keyboard, often by someone who has never had to write their own address for a stranger. It arrives abbreviated, misspelled, missing the directional that makes it unambiguous, carrying an apartment number in a field that wasn't meant for one, or naming a building rather than an address. The reference data is no better behaved: OpenStreetMap spells the same street three different ways within a mile.

Why Not Google

We looked hard at Google's Geocoding API and rejected it for two reasons, one obvious and one structural.

The obvious one was price. Per-thousand pricing is fine when your query volume is a rounding error and ruinous when geocoding sits in the hot path of every order, every address edit, every merchant onboarding, and every batch backfill someone kicks off on a Tuesday.

The structural one mattered more, and it's the one people miss: under the terms we were operating under, we weren't allowed to keep the results. Caching was permitted only briefly — we understood it as a day — and permanent storage of the returned coordinates was not on the table.^[1] That single restriction changes the shape of the cost curve completely. Delivery addresses are the most repetitive data a consumer platform has: the same diner orders to the same apartment forty times a year, and the same thousand office towers absorb a disproportionate share of the lunch rush. With permanent caching, geocoding is a one-time cost per distinct address and your bill flattens as the address book saturates. With a one-day TTL, it's a recurring cost per query that grows with order volume forever. We would have been paying, repeatedly, for an answer that had not changed and would never change.

There was a third objection that didn't need a spreadsheet: this is the first call in the order path. Putting a third-party network dependency there means their outage is our outage, their latency is our conversion rate, and their idea of a good match is our idea of a good match whether we agree or not.

Why Not Nominatim

The obvious open-source answer is Nominatim, the search engine that powers openstreetmap.org.^[2] It's good software solving a harder problem than ours. Nominatim is a worldwide, general-purpose full-text search over every kind of OSM object — it will find you a mountain, a pub, a postcode, or a street, in any country, in any language, from an unstructured query.

We had exactly one query shape: a US street address, in a metro we operated in, that needed to become a point. Generality we didn't need cost us in the two places we cared about. Latency, because that flexibility is paid for in the query plan. And control, because the part we most needed to own was the ranking — and specifically the confidence semantics. We didn't want the best match; we wanted a match plus a defensible statement of how much to trust it, because the product behaved differently at different tiers. A general-purpose relevance score doesn't decompose into "this is a rooftop point" versus "this is a guess between two known houses eighty numbers apart."

So we built a narrow one. The whole US index fits in memory on a normal service instance, answers in the low single-digit milliseconds, and every scoring weight in it was ours to move.

Why Not CRP

Worth saying explicitly, because the routing work on this site keeps reappearing: the geocoder shares nothing with the CRP routing engine but the source data. Routing needs topology — which segments connect, which way traffic flows, what turns are legal, how long each edge takes right now. Geocoding needs none of that and would be slowed down by carrying it. What geocoding needs is names and house numbers, including on ways no vehicle may drive: a pedestrianized block still has addresses on it, and a courier still has to find them. The two systems were built from the same OSM extract by different pipelines and deployed as different services.

Standardization Is the Whole Game

The single highest-leverage decision in the design is that query strings and reference data go through the same parser. Not a similar one — the same code path.

That parser follows USPS Publication 28^[3], the standard that defines how American addresses are written: uppercase everything, drop the punctuation that carries no information, split off the secondary unit designator (APT, STE, FL, a bare #), pull the ZIP and state off the end, and decompose what's left into house number, pre-directional, street name, standardized suffix, and post-directional. AVENUE, AVE, AVEN and AV all become AVE. NORTH and N. both become N. EIGHTEENTH and a bare 18 both become 18TH.

Run that over the reference data and a mess resolves itself for free. In this Chicago extract, "North LaSalle Street", "North Lasalle Street" and "N. La Salle St." aren't three candidates for a fuzzy matcher to agonize over; they're one key, N LASALLE ST, computed twice. 547 distinct OSM street spellings fold into 535 logical streets before any similarity measure runs at all. Every variant you can normalize away is a variant your fuzzy matcher no longer has to get right — and fuzzy matching is where the wrong answers come from.

The directional carries more information than the suffix. This is the counterintuitive part, and it falls out of how American grid cities are laid out. 200 N Michigan and 200 S Michigan are both real, both in Chicago, and about a quarter mile apart — and the strings differ by a single character. Meanwhile "Dearborn Street" versus "Dearborn Parkway" is a much larger string difference describing two streets that are, in the scheme of things, near each other. Pure edit distance has this exactly backwards. So the scorer treats a directional that disagrees outright not as a typo but as evidence of a different street, and multiplies the whole score by 0.55 — while a directional that's simply missing on either side stays neutral, because plenty of people write "Michigan Ave" and mean it.

Three Indexes, Because They Fail Differently

Retrieval and ranking are separate problems. Ranking can afford to be expensive because it runs over a shortlist; retrieval has to be cheap because it runs over everything. The service kept three inverted indexes over the standardized street keys, and a query hits all of them.

Exact key. The common case and the cheap one. Because both sides were standardized identically, a large majority of real queries hit a hash lookup and never touch a similarity measure at all. Relaxed variants — the key without its suffix, the key without its directional — catch "N Michigan" and "Michigan Ave".

Trigram index. The retrieval workhorse for everything else. Every street key is shredded into padded three-character windows; a query is shredded the same way and scored by how many windows it shares. This is what turns 535 streets into a shortlist of forty without comparing the query to each one. It's robust to insertions, deletions and transpositions, and it degrades gracefully. What it's bad at is short names and sound-alikes, because a word can be pronounced identically while sharing very few three-character windows.

Phonetic index. Which is why the third arm exists. Street names are overwhelmingly proper nouns — surnames, mostly — and people misspell proper nouns phonetically. Metaphone^[4] reduces a name to a consonant skeleton approximating how it sounds, so DEERBORN and DEARBORN both code to TRBRN and land in the same bucket. Try sound-alike in the demo and watch the ph column: trigram overlap on that query is a weak 0.47, and the phonetic agreement is a large part of what separates Dearborn Street from the four other candidates it's tangled up with. When a misspelling is bad enough that trigram overlap drops below the shortlist cutoff entirely, this is the only arm that retrieves the street at all.

The final score is a weighted blend of trigram overlap, normalized edit distance, phonetic agreement, directional agreement, suffix agreement and ZIP consistency, with the directional penalty applied on top. The demo prints the full breakdown for every candidate, so you can watch which arm is actually carrying a given query — and watch the blend disagree with any single measure taken alone.

Placing the House Number

Picking the street is half the job. The other half is putting a number on it, and this is where a geocoder should be honest about what it knows. Four tiers, in descending order of trust:

Rooftop. We hold an actual coordinate for that exact house number on that exact street. Nothing to compute; return the point. In dense downtown Chicago, OSM's address point coverage is good enough that this is the common outcome — and when several points share a number, they're units in one building, which is a fact worth surfacing rather than silently collapsing.

Interpolated. We don't have the number, but we have numbers on either side of it. Find the bracketing pair of the same parity — odd and even are opposite sides of the street, and mixing them puts you across four lanes of traffic — and walk the fractional distance between them. This is the classic TIGER-style range interpolation, and it is a genuinely good estimate when the anchors are close together and a genuinely bad one when they aren't. So the demo says which two points it interpolated between, what fraction of the way it landed, and warns you outright when the gap is wide. Try misspelled: 300 N Michigan interpolates between 230 and 316, and the result reports the 86-number gap it's guessing across rather than presenting itself as a fact.

Street. We're confident about the street and not about the number — usually because the number falls outside the range we hold. The temptation here is to quietly return the nearest end of the street, which reads as a successful match and is how a courier ends up two blocks away wondering why the building numbers are going the wrong direction. It clamps, but it says so. Try out of range.

ZIP. The floor. Enough to say which part of the city, not enough to dispatch on.

Those tiers weren't decoration; they drove product behavior. A rooftop match went through silently. An interpolated one dispatched but pushed the raw address text prominently into the courier app, because the pin might be off by a building. Anything below that stopped and asked the diner to confirm, which is annoying exactly once and much cheaper than a delivery to the wrong address.

Reverse: The Same Problem, Mirrored

Reverse geocoding — coordinate to address — looks trivial and isn't, because the obvious implementation is wrong in a specific and recurring way. Nearest address point wins sounds right until you notice that "nearest" is measured through walls. A point fifteen meters away on the far side of a building is not the address anyone wants; the one forty meters away that fronts the street you're actually standing on is.

So the answer is assembled from two independent lookups that are allowed to disagree. One finds the nearest address points via a uniform spatial grid. The other finds the nearest street centerline, projects onto it, decides which side of the centerline the query falls on by the sign of a cross product, and interpolates a house number from the bracketing points that front that same side — snapping the result to the block's parity, because an even number on the odd side is a bug and not a rounding error.

Two details earn their keep. Centerlines are weighted by road class before distance is compared, because a riverwalk esplanade or a service alley is frequently the closest line to a click on Michigan Avenue and is never the street a building is addressed on. And when the two lookups disagree, the demo shows both and says why — the disagreement is usually the most informative thing on the screen.

The USPS Fallback

Some addresses simply aren't in OSM, and some inputs aren't addresses at all — try landmark, not an address, which is a real building that a great many people will cheerfully type instead of its street address. When nothing cleared the acceptance threshold, the request left our index and went to the USPS Web Tools Address Standardization API.^[5]

It's important to be clear about what that bought us, because it isn't a geocoder. USPS will not give you a coordinate. What it gives you is authority on whether the address exists and is deliverable, plus a properly standardized set of components and a ZIP+4 — which is a much sharper instrument than it sounds, since a ZIP+4 typically identifies one side of one block. So the fallback answered a different question than the primary path, and that's exactly why it was worth having. A miss in our index became one of three specific outcomes instead of a shrug: the address is real and we're missing data (accept it, fall back to ZIP-level positioning, flag the gap for the next data refresh), the address is real but the diner typed it loosely (re-run our matcher against the USPS-standardized form, which frequently hits), or the address isn't deliverable at all (stop and ask, before a courier is involved).

It sat behind the threshold rather than in front of it for the usual reasons — it's a network call with rate limits, it's slower than an in-memory lookup by orders of magnitude, and it has nothing to say about the ninety-plus percent of queries our own index answers well. The fallback is for the tail, and the tail is where the expensive failures live.

About the Demo

Everything below runs in your browser against a real OSM extract of downtown Chicago — 16,405 address points, 5,632 named street ways folded into 535 logical streets, fetched from the Overpass API. The index builds in well under a hundred milliseconds and every query runs live: the parser, the three retrieval arms, the scoring blend, the interpolation and the reverse lookup are the real implementations, not a canned trace. The example chips each exercise a different failure mode, and the panel shows every stage's intermediate state rather than just the answer.

Honest idealizations. The city name table covers this metro rather than the full USPS City/State file; the production parser consulted the real one. The USPS fallback is described but not called — it needs a credentialed server-side request, so the demo shows you where the handoff happens and what it would have asked. Downtown Chicago's OSM data is unusually point-rich, so interpolation appears less often here than it did nationally, where TIGER-derived address ranges carried far more of the load. And the production service was a JVM service holding the whole US index in memory behind a load balancer, not a browser tab holding one city. The structure — one parser on both sides, three inverted indexes, a weighted blend with a directional penalty, parity-aware interpolation, tiered confidence, and a deliverability backstop — is the real thing.