Today I decided to over-engineer address autocomplete instead of using google api

I am building Astroku, a back-office app for real-estate agencies. People in it type addresses all day, so it needs address autocomplete: you type a few characters and pick the right address from a list.

The usual answer is Google Places. It works, and it charges per request or per session. For an app where typing addresses is most of the job, that bill grows with every keystroke of every user, and I would rather not have it.

Australia also publishes its national address file as open data. It is called G-NAF, and the August 2026 release has 16.1 million addresses. So the data is free. The question was whether I could search it well enough, and cheaply enough, to skip the paid API.

This post is what I built, what went wrong on real data, and how it measured. You can try it at address.rapidsd.com.

The ideas I dropped

A database with full-text search. Load the addresses into Cloudflare D1 or Postgres and query on each keystroke. This is the obvious design. It also means running a database with 16 million rows, and a server round trip for every key pressed.

A key-value prefix index. Store every prefix of every address as a key, so “200 geo” points straight at its matches. Lookups are fast, but the number of keys is huge, and a prefix index has no answer for a typo. One wrong letter and the key is not there.

Static files, no server. This is the one that stuck. Build plain JSON files once, put them on a CDN (a network of servers that keeps copies of files close to users), and let the browser read them itself.

What made the third idea possible is one observation: people mistype street and suburb names, not numbers. So fuzzy matching, meaning matching that tolerates spelling mistakes, only has to cover the names. G-NAF has 16.1 million addresses but only 122,000 distinct street names in 15,500 suburbs. Those two lists are about 600 KB compressed. A browser can download them once and keep them.

How it works

A builder script reads G-NAF and writes 668,987 small JSON files:

• Two lists, downloaded once: every suburb with its state and postcode, and every distinct street name with how common it is.
• One file per street name, listing every street in the country with that name. “Railway” is the largest, with 949 streets.
• One file per street, listing every address on it.

A search then goes like this. The browser corrects the typed words against the two lists in memory, using edit distance: the number of letters you would have to change, add, remove or swap to turn one word into another. One or two wrong letters are allowed, the first letter included. Words under four letters must be spelt right. Then it fetches at most 6 street-name files and 4 street files (8 when a unit was typed), and filters the addresses.

Each street in a name file carries a short summary: how many addresses it has, its lowest and highest number, its highest unit number, and its centre point. The summary does two jobs. First, the search can skip streets that cannot hold the typed number or unit without opening them. In one real query for a unit with no suburb typed, 276 streets shared the name, and only 7 could hold the address. Only those were opened. Second, the centre point lets the search rank streets by distance from a point the page supplies, such as the agency’s office. The code never asks the browser for its location, so there is no permission prompt.

Some searches on the real data, with their first result:

Typed	Found
200 gorge st sydny	Level GG, 200 George Street, Sydney NSW 2000
8 whitman st southbank	8 Whiteman Street, Southbank VIC 3006
50 brigde road richmond 3121	48-50 Bridge Road, Richmond VIC 3121
suite 2 249 pitt st sydney	Suite 2, 249 Pitt Street, Sydney NSW 2000

Building all of this takes 5 minutes 20 seconds on a laptop and peaks at 5.7 GB of memory. The output is 3.0 GB. The largest single file a browser might fetch is 76 KB compressed (St Kilda Road in Melbourne, 11,187 addresses), so nothing needed splitting.

What real data broke

It passed its tests on a small made-up data set. Then I ran it on the full file.

• It was slow. A search took 100 to 290 ms. The matching code created new arrays for every comparison, and it scanned every street name on every search. Now it reuses its memory, and the full scan only runs when nothing else matched. A search takes 4 to 36 ms of computation. The full-scan fallback takes about 65 ms.
• Unit and level codes. G-NAF has its own code tables: 276 street types, plus codes for units, levels and suffixes. “SE” means Suite. I had guessed at a few of these. Now they are generated from the release’s own tables.
• Towers crowded the list. An office tower has hundreds of units and floors, each a separate record, and they pushed everything else out of the results. Floors and units now count as parts of one building. Some buildings have no plain record at all: there is no “200 George Street”, only its floors and shops.
• Spaced unit forms. 4/22 worked. 4 / 22, 4, 22 and 4 22 did not: the unit was read as the street number, and the number as part of the street name.
• Finished word or half-typed word. A street name followed by a type or a suburb is finished, but it was still matched as if the person were halfway through typing it. Longer names that start the same way crowded out the name that was one letter off.
• “cir” means Circle. I read it as Circuit. It is G-NAF’s abbreviation for Circle.
• A suburb that starts like a state. A last word beginning “vic” was read as Victoria, when the person was partway into a suburb name.

The last three came out of the accuracy test below.

Hosting

The files sit in a private Cloudflare R2 bucket (R2 is Cloudflare’s file storage). Nothing in it is public. A Cloudflare Worker, a small program that runs on Cloudflare’s servers, stands in front with two doors:

• The API. A normal HTTP search API with access keys, rate limits and usage recording. Each keystroke asks the server. Suggestions are free; fetching the parts of the picked address is the billable step, so one lookup is one address entered, however many keys it took.
• The files. The browser asks for a signed token that lasts through the next day, then reads the files through Cloudflare’s cache and does the matching itself.

I expected the token check to cost something. Measured from Sydney, a token-gated file took a median of 61 ms and a plain static file with no Worker code took 64 ms. So it adds nothing measurable. Most of that time is opening a new connection.

Uploading 668,987 files took about 25 minutes, roughly 455 files a second.

Speed

The benchmark types six public addresses, three of them misspelt, one key at a time against the live service: 94 keystrokes, waiting for each answer. I ran it in Chrome from Sydney on 14 November 2026, using Chrome’s network and CPU throttling. Times are medians per keystroke.

Network and device	API	Files: first wait	Files: first visit	Files: later
Broadband, fast laptop	50 ms	0.4 s	16 ms	8 ms
Fast 4G	174 ms	1.6 s	16 ms	8 ms
Slow 4G	575 ms	6.9 s	16 ms	8 ms
Slow 3G	2.0 s	24.5 s	16 ms	8 ms
Broadband, CPU 4× slower	50 ms	0.7 s	53 ms	34 ms
Broadband, CPU 6× slower	50 ms	0.5 s	72 ms	52 ms
Slow 4G, CPU 4× slower	575 ms	7.0 s	69 ms	35 ms

The API costs one round trip per keystroke, whatever the device. The files cost almost nothing per keystroke once loaded, but there are two catches. A first visit has to download the two lists before the first suggestion appears, which is 6.9 seconds on Slow 4G and 24.5 seconds on Slow 3G. And about one keystroke in ten fetches a new street file: at the 90th percentile (p90, the time that nine keystrokes in ten beat) that is 51 ms on broadband, 1.4 s on Slow 4G and 4.8 s on Slow 3G.

Against the paid services

I ran the same six-address test against Addressfinder, Geoscape Predictive, Google Places Autocomplete (New) and Mapbox Search Box. Then I ran an accuracy test: 150 addresses sampled at random from the built files, each sent three ways. Typed correctly, with one slip in the street name, and cut off three letters into the suburb. “Found” means the right address was in the first five suggestions.

Service	Broadband	Slowest 1 in 10	Fast 4G	Found	With a typo	Cut off
Our files, later visits	8 ms	15 ms	8 ms	100%	100%	100%
Our API	44 ms	79 ms	174 ms	100%	100%	100%
Addressfinder	43 ms	154 ms	171 ms	99%	99%	99%
Geoscape Predictive	84 ms	152 ms	178 ms	97%	79%	97%
Google Places Autocomplete (New)	141 ms	174 ms	174 ms	98%	79%	98%
Mapbox Search Box	298 ms	430 ms	319 ms	85%	85%	82%

The same accuracy figures, with how often the right address was the first suggestion in brackets:

Service	Typed correctly	One typo	Stopped mid-suburb
Ours	100% (100%)	100% (100%)	100% (100%)
Addressfinder	99% (99%)	99% (95%)	99% (97%)
Geoscape Predictive	97% (97%)	79% (77%)	97% (96%)
Google Places Autocomplete (New)	98% (92%)	79% (75%)	98% (96%)
Mapbox Search Box	85% (85%)	85% (84%)	82% (71%)

Do not read these tables as “ours is the best”. Read the caveats first.

• The test is small. Speed comes from six addresses and 94 keystrokes. Accuracy comes from 150 addresses, 450 requests per service.
• Our row is a rerun after fixes. Our first run scored 99%, 93% and 99%. The misses showed the three bugs listed above (finished words, “cir”, the suburb that looks like a state). I fixed them and ran the same sample again. The other services got one attempt.
• The held-out check is ours only. On a fresh sample the fixes had never seen, ours scored 100%, 99% and 100%. I did not rerun the other services on it.
• The sample suits G-NAF services. The addresses come from G-NAF itself, which ours, Geoscape and Addressfinder are all built on.
• Suburb matching is strict. A result counts when its number, street name and suburb match. A service that names a suburb differently is marked wrong, even if a person would accept the answer.
• The speed tail is rough. The p90 figures moved by up to 90 ms between runs. Ours ranged from 65 to 166 ms, Addressfinder’s from 91 to 154 ms.
• Fast 4G is a floor. Chrome’s Fast 4G throttle adds about 170 ms to everything, so in that column only Mapbox is visibly slower than the rest.
• One location, no load. Everything was measured from Sydney. Times from elsewhere, and behaviour under load, are not measured.

Where mine is worst: how much you have to type

Finding the address is one thing. How many characters you type before it shows is another, and here mine is last.

On the six well-known addresses, Google needed 5.5 characters of about 21 and mine needed 9.7. All six are prominent commercial addresses, and Google ranks prominent places first, so I ran it again on the 150 ordinary addresses, typing each one key by key.

Service	Found, of 150	Characters typed, of 25
Geoscape Predictive	145	8.5
Mapbox Search Box	127	9.3
Google Places Autocomplete (New)	147	9.4
Ours	150	10.0

The averages are over the addresses each service found, so a service that gives up on the hard ones looks a little better than it is. On the 122 addresses all four found, the order is the same: Geoscape 8.6, Google 8.9, Mapbox 9.3, ours 10.0. Addressfinder was not part of this test.

So mine finds more, and makes you type about one character more to get there. Head to head with Google, Google showed the address first on 61 of the 150, mine on 34, and they tied on 52. Against Geoscape it is more lopsided: Geoscape was three or more characters ahead on 29 addresses, and mine on 5.

Part of the reason turned out to be simple, and I fixed it later the same day. That is below.

Then I over-engineered it further

The first version left four holes that I could see, and one the typing test above had just shown me. I closed them the same day.

The API first, then the files. The files are fastest, but a first visit waits for the lists to download: 6.9 seconds on Slow 4G. So the lookup now starts on the API, which needs nothing downloaded, and times its own answers. After three answers with a middle time of 400 ms or less, it fetches the lists in the background and moves to the files. If the browser reports a slow or metered connection it never fetches them. On a slow connection it stays on the API and waits longer between searches: with answers taking 900 ms, typing 26 characters sent 5 searches, not 26. If the files turn out slower than the API was, it goes back.

I also tried one more thing for very slow connections: stop searching while typing, and search once when the field is left. It worked as written and felt wrong in use. Suggestions that appear after you have moved on are worse than suggestions that arrive late. I took it out, and a slow connection now only lengthens the wait, up to one second.

A cache for answers. The answer to a search depends only on the text, the options and the data version. The Worker now keeps each answer in Cloudflare’s cache for a day, shared by every account. The key and the rate limit are still checked first. Measured from Sydney on one connection, twelve half-typed addresses took a median of 87 ms the first time and 38 ms the second.

A default place to rank near. “5 George St” fits hundreds of streets. Cloudflare already knows roughly where each request comes from, by IP address, to about the nearest city. A search from a browser that names no point is now ranked near that. The browser asks no permission, and searches from a server are left alone.

Building names. G-NAF holds 141,000 distinct building names: shopping centres, towers, retirement villages, farms. Many are noise. 7,705 addresses in New South Wales alone are in a building called “(RETAIL)”, and 1,298 are in “BUILDING A”. Those are dropped. The rest go in a third list, with one file per name. So “queen victoria building”, “eureka tower” and “shop 10 chadstone shopping centre” now work, typos included. The price is size: the building list is 734 KB compressed, larger than the street names, so a browser reading the files loads it in the background and searches without it until it arrives.

Other names for the same thing. G-NAF also records about 41,000 alternative street names, 4,400 other names for suburbs, and 880,000 addresses that are another way of writing a principal address: a corner block’s second street, or one number out of a range. I had been throwing all of these away. They are searchable now, and an alias is hidden when the address it stands for is already in the list.

Reach while typing. This is the hole the typing test showed. With a street name half typed and no suburb yet, the search opened the four largest candidate streets, and the list filled with several units of the same one. I first opened eight, across up to ten candidate names. That brought the average from 10.0 characters typed to 9.4, level with Google, and it made the service slow: a Worker opens six connections at a time, so eighteen file reads queued in rounds, and a keystroke on uncached files went from under 100 ms to as much as half a second. So it opens six of each now, one round, and shows the best match on each street before a second match on any. That gives about 9.7 characters, on these 150 addresses and on a second set of 150 the change had never seen. Better than 10.0, still behind the other three.

All of that made the build bigger: 820,517 files and 3.7 GB, built in 6 minutes 40 seconds.

What it cost, and what is next

It cost a day of my time, a 5-minute build and a 25-minute upload. Cached reads from R2 cost nothing, and the matching runs in the user’s browser. I have not measured a monthly hosting bill, so I will not quote one.

What is not done:

• Ranking while typing. The others still get there a little sooner, Geoscape by about a character.
• Levels in typed text. “Level 3, 22 …” is not parsed. Levels still show in results.
• Places G-NAF does not name. A building is found only under the name G-NAF holds for it. “QVB” finds nothing.
• A house number with no suburb. A plain number and a common street name fit most streets of that name in the country. The streets with the most addresses come first, unless the search knows a state, postcodes or a nearby point to prefer.
• New addresses. G-NAF is released quarterly, so new subdivisions are missing for a while. The widget can offer the text as typed as a last option.

Was it over-engineered? Yes. A paid API would have been one afternoon. But suggestions now arrive in 8 ms with no charge per keystroke, and I know exactly why each result is where it is.

Licence

G-NAF is open data under the Open G-NAF End User Licence Agreement, and that licence requires attribution. The demo’s attribution is at address.rapidsd.com/licence. If you build on the same data, read the current licence yourself before you sell anything made from it.