geocoder

A point-in-region lookup engine for WGS-84 coordinates, built around a packed Hilbert R-Tree that reads its index from a memory-mapped binary file. Designed for read-heavy workloads (millions of lookups per second) on server-class hardware.

The engine is shipped as a Go library, an HTTP/JSON server, and a gRPC service. It accepts a (lat, lon) pair in degrees and returns the polygon ID of the region that contains it.

What this is

• A read-only geographic lookup service. The .bin index is built once (offline) and queried many times.
• In-memory after mmap. The kernel pages the file into the process address space on demand; the application does not load it eagerly.
• Zero-allocation on the hot path. A Lookup call performs no heap allocation, so GC pressure stays flat under sustained load.

What this is not

• Not a general-purpose GIS engine. It answers "which region contains this point" and nothing else (no spatial joins, no routing, no geometry editing).
• Not a spatial database. There is no indexing API at runtime, no query language, and no ACID guarantees. The index is rebuilt offline when the source data changes.
• Not portable across CPU architectures. The binary file format uses native-endian int32 and is not byte-swapped on read. Generate the .bin on the host that serves it.

Quickstart

Build the server and feed it a Natural Earth countries index.

# 1. Get the source data (or supply your own GeoJSON).
curl -fsSL \
  https://raw.githubusercontent.com/nvkelso/natural-earth-vector/master/geojson/ne_10m_admin_0_countries.geojson \
  -o data/countries.geojson

# 2. Convert to the binary index.
go run ./cmd/builder \
  --input  data/countries.geojson \
  --output data/countries.bin \
  --tolerance 0.005

# 3. Serve it.
go run ./cmd/geocoder \
  --db   data/countries.bin \
  --http :8080 \
  --grpc :9090

# 4. Query.
curl 'http://localhost:8080/lookup?lat=55.7558&lon=37.6173'
# {"found":true,"polygon_id":643,"latency_ns":9170}

The polygon ID 643 is ISO 3166-1 numeric for Russia (Natural Earth ships ISO_N3 for each country). Substitute any other GeoJSON with the same schema to index your own regions.

Performance

Numbers below are from BenchmarkRealDataLookup and BenchmarkHTTPServer on a Ryzen 5 5500U (12 threads) with Go 1.26.3, running the Natural Earth admin-0 dataset (4 289 polygons, 283 102 vertices after Douglas-Peucker at ε=0.005°).

Operation	Time	Allocations
Engine Lookup (in-process)	9.2 µs	0
HTTP GET /lookup (warm, hit)	23 µs	5
HTTP GET /lookup (warm, miss)	15 µs	5
LoadMmap (10 000 polygons)	12.8 µs	3
LoadMmap (100 000 polygons)	28.1 µs	3

The engine hits roughly 9 µs per lookup on the real dataset because each call performs only:

1. One recursive descent through a Hilbert-packed R-Tree (about four levels for 4 289 polygons).
2. A 16-byte bbox pre-filter per polygon candidate in a leaf.
3. A ray-cast (PNPOLY) only on polygons whose bbox contains the query point.

Numbers will be lower on synthetic data (≈1 µs per call on a thousand small squares) and higher on denser inputs.

See docs/performance.md for the full benchmark methodology and the CPU profile analysis that justified the bbox pre-filter.

Architecture

A geocoder deployment has two phases.

Note

The phases are separate processes. The builder writes the .bin file once. The server memory-maps that file at startup and never writes to it.

Offline: build the index

GeoJSON FeatureCollection
        |
        v
  GeoJSON parser          (internal/geojson)
        |
        v
  Douglas-Peucker          (internal/simplify)
        |
        v
  Packed Hilbert R-Tree    (internal/index)
        |
        v
  Binary file (.bin, v2)   (internal/index.Save)

The cmd/builder CLI runs this pipeline. The output is a flat binary file that contains the R-Tree, polygon metadata, and a vertex store laid out as two parallel int32 arrays (Structure-of-Arrays, SoA).

Online: serve the index

mmap'd .bin file  -->  Tree (zero-copy slices)  -->  Lookup(lat, lon)
                                                       |
                                                       v
                                                 polygon_id, hit/miss

The cmd/geocoder binary loads the file via mmap (PROT_READ, MAP_SHARED) and exposes Lookup over HTTP/JSON and gRPC. No data is copied off the mmap region.

Project layout

api/geocoder/             Protobuf contract + generated Go bindings.
cmd/builder/              Offline CLI: GeoJSON -> .bin.
cmd/geocoder/             Online binary: HTTP + gRPC server.
data/                     Sample .bin file (Natural Earth admin-0).
                          GeoJSON files are gitignored.
docs/                     Detailed documentation (this file plus
                          architecture, file format, performance,
                          CLI usage, server API).
internal/geometry/         Point, BoundingBox, Haversine helpers.
internal/simplify/        Douglas-Peucker line simplification.
internal/geojson/         FeatureCollection decoder.
internal/index/           Tree, Build, Save, LoadMmap, Lookup, PNPOLY,
                          Hilbert packing, per-polygon bbox pre-filter.
internal/server/http/     HTTP/JSON handler.
internal/server/grpc/     gRPC handler.
scripts/e2e_benchmark.sh  End-to-end benchmark on real-world data.

The internal/ directory follows the Go convention: those packages are only importable from inside this module. The cmd/geocoder binary and the cmd/builder binary live in the same module and therefore can use the engine directly.

API

HTTP

GET /lookup?lat=<float>&lon=<float>

Returns:

{"found": true, "polygon_id": 643, "latency_ns": 9170}

or, if the point is outside every polygon:

{"found": false, "latency_ns": 8730}

A health endpoint is also exposed at GET /healthz.

gRPC

service Geocoder {
  rpc Lookup(LookupRequest) returns (LookupResponse);
}

message Point         { double lat = 1; double lon = 2; }
message LookupRequest { Point point = 1; }
message LookupResponse {
  bool   found      = 1;
  uint32 polygon_id = 2;
}

The service is registered in api/geocoder/geocoder.proto. The generated Go bindings live in api/geocoder/geocoder.pb.go and api/geocoder/geocoder_grpc.pb.go.

Go library

import "github.com/kshishtovsky/fast-geocoder/internal/index"

tree, err := index.LoadMmap("data/countries.bin")
if err != nil { /* … */ }
defer tree.Close()

id, ok := tree.Lookup(55.7558, 37.6173)  // returns 643, true

Tree is safe for concurrent reads. Lookup performs no heap allocation, so a goroutine-per-request server can scale to the number of in-flight TCP connections without adding GC pressure.

Building from source

You need Go 1.26 or newer and protoc with the protoc-gen-go and protoc-gen-go-grpc plugins.

# Regenerate the protobuf bindings after editing geocoder.proto:
PATH="$HOME/go/bin:$PATH" protoc \
  --proto_path=api/geocoder \
  --go_out=api/geocoder --go_opt=paths=source_relative \
  --go-grpc_out=api/geocoder --go-grpc_opt=paths=source_relative \
  api/geocoder/geocoder.proto

Build the binaries:

go build -o bin/builder   ./cmd/builder
go build -o bin/geocoder  ./cmd/geocoder

Running the tests

go test ./...

The repository includes the Natural Earth .bin under data/ so BenchmarkRealDataLookup and TestRealWorldLocations can run without an internet connection. Regenerate it with scripts/e2e_benchmark.sh if you need a fresh build.

Limitations

The following are known limitations, not goals:

• Single-file index. There is no support for partitioning the index across multiple files or sharding by region.
• No incremental updates. A change in the source data requires rebuilding the whole .bin file.
• No streaming RPC. The gRPC service exposes only unary calls. Adding a LookupMany or a server-streaming variant is a deliberate non-goal until profiling shows it's needed.
• No TLS by default. Both HTTP and gRPC listen in plaintext. Run behind a TLS-terminating proxy (nginx, Envoy, etc.) for production deployments.
• Native-endian binary format. Files generated on a big-endian host cannot be loaded on a little-endian host. The library rejects the file with a clear error in that case, but you must rebuild.

Next steps

• Architecture overview — package layout and data flow.
• Binary file format — the on-disk .bin layout, including the v2 header and the per-polygon bbox section.
• Performance notes — full benchmark table and the CPU profile that drove the bbox pre-filter.
• Server API — flags, HTTP endpoints, gRPC contract, and graceful-shutdown semantics.
• Builder CLI — GeoJSON loading, simplification defaults, and per-polygon statistics.