ellen's disorganized thoughts

Over the last few weeks I’ve been hard at work building a FOSS maps app for Android from the ground up based on Material 3 components and industry standard maps tooling. It has online and offline modes, and integrates well with self-hosted maps services like Headway deployments. I’m really quite pleased with it and I hope others enjoy using it as much as I’ve enjoyed making it. I’m about 2 weeks in to development so expect some bugs. But it has most of the features you’d expect like search, directions and navigation. It’s shockingly usable already.

I’ve been yearning for something better in the FOSS maps space for a long time. I don’t think I’m the only one. I’m really hopeful that Cardinal Maps can grow into that something for myself and others.

If you’re stoked about this project I’d appreciate contributions and beta testers. There’s an obtainium link in the repo README.md if you want updates.

Thanks for reading!

In 2022, I started the Headway maps project, aiming to democratize maps services by making it easy to self-host your own web maps based on OpenStreetMap data. The project was well received, but to this day it is notably missing transit support for the majority of the planet. It began its life as a transit-focused OpenTripPlanner frontend designed for regional deployments, but transit support took a back-seat as the need to scale became apparent. It turns out people like maps services more when those services work for getting around their own region, who knew?

At some point I became aware of the RAPTOR algorithm for transit routing, and in early 2024 I attempted to implement it to provide an infill service for the areas of the planet that maps.earth doesn’t host an OpenTripPlanner instance for. It was a bit of a false start. It’s a difficult thing to implement without errors. Imagine the a computer science student’s first time implementing quicksort and you’re on the right track. The code languished and was forgotten.

Now, in December 2024, I decided to plan a trip to California on a train. I did what any self-respecting transit nerd with a computer science degree would do—create her own transit routing software to plan her journey. I ended up hyper-focusing on the project so much that I missed my train and cancelled the trip, but that’s a story for another time. Starting from the husk of my old project and fueled by caffeine, I pretty quickly identified some of the major deficiencies and fixed them.

The result is hosted at https://farebox.airmail.rs/plan/<from>/<to>/ and accepts lat,lng pairs for each argument. It will also attempt to geocode addresses and POIs on a best-effort basis. Code for setting up your own is available on the GitHub repository. This instance is hosted in a tmux on my home server so don’t expect “miracles” or “uptime”. I sometimes even turn that server off if I have a telemedicine appointment or a big meeting.

Some sample queries

Note for posterity: These are all broken since the API changed.

Between two parks in major US cities: https://farebox.airmail.rs/plan/Central%20Park,%20NYC/Millennium%20Park%20Chicago/

My favorite bakery to my favorite cheese shop: https://farebox.airmail.rs/plan/Lazy%20Cow%20Bakery%20Seattle/Cultured%20Kindness%20Portland/

Across the continental United States: https://farebox.airmail.rs/plan/Westlake%20Station%20Seattle/Central%20Park%20NYC/

Feel free to play around with it or set up your own. It’s pretty light on resources. My global instance took about 24 GiB of memory to build its timetable and consumes around 3 GiB to serve the data.

What else is out there

The notable alternatives to Farebox (working title, if you have ideas for better names let me know!) include OpenTripPlanner, MOTIS (see also: Transitous), Valhalla, and that’s about it to my knowledge. I’m omitting GraphHopper because last I checked it only works for a single GTFS feed. My “global” instance uses ~500, for comparison.

Of these, only MOTIS and Valhalla are capable of routing at this scale. I haven’t been able to extensively test either head-to-head, but from the spot checking I’ve done Farebox performs favorably against MOTIS, at least.

Where we go from here

There are still some issues preventing Farebox from correctly responding to some queries. For instance, it’s sometimes capable of serving routes from Barcelona to Berlin (in about a second, compare to MOTIS’s ~50s) but with the current timetable build those queries aren’t returning results.

The API also needs some work before it’s consumable by a downstream application. But that’s a project for another day. :)

Disclaimer: I did not quantifiably break SOTA, but I claim my parser is dramatically better than SOTA for geocoding purposes, for reasons I elaborate on.

Street address parsing is a very hard problem. It’s one of those topics that I could write a pages-long “Myths programmers believe about X” think-piece on. For the curious, Al Barrentine’s post on the subject announcing libpostal 1.0 is a must-read. For our purposes, suffice to say it’s a tough nut to crack.

The state of the art circa 2024

Libpostal is the ultimate address parser for people who don’t make typing errors. It is unmatched, remains unmatched, and after toiling at this problem for a few weekends with modern NLP tools like transformers, I have personally concluded that nobody will be able to beat the novel CRF architecture of libpostal for well-formed queries for a long time. Libpostal’s dominance comes from its ability to simply memorize everything. The vocabulary is enormous, and the CRF weights are very sparse, which allows it to parse a query in close to 100μs. This memorization comes with two big downsides that motivated my search for a better (but also worse) address parser.

Libpostal downside 1: The model is enormous.

The SOTA libpostal model weighs in at ~2.2GiB after post-processing for sparsity, and it all needs to be in RAM for parsing to work. It currently can’t be memory mapped due to some of the complexities of the on-disk format. For the geocoder I’m working on, Airmail, storage and memory requirements like that are a deal-breaker.

Libpostal downside 2: Typos and prefix queries

Unfortunately for those of us out there working on geocoders, libpostal breaks when presented with typos or partial queries. For example, if you ask libpostal to parse the address “1600 pennsylvania ave nw washingto”, it will tell you that 1600 is a house number (great!) and “pennsylvania ave nw washingto” is a street (less great).

Libpostal’s CRF-based architecture is approachable and comprehensible, rare in the machine learning world. Because of its approachability, I’m willing to claim that I know why this case fails. Simply put, Libpostal has an enormous vocabulary that it uses very opportunistically. “Washington” is a highly predictive token, so libpostal’s CRF rightly assigns a very high weight to it being p