Compact Maps - What Can You Put in 12 MB Binary?

Why do we call our self-hosted mapping solution "Compact Maps"? Well, because it is... compact. The complete set of standard WEB map APIs - map tile retrieval, geocoding/reverse geocoding, and routing - is embedded into one single Linux executable. Map data is stored separately, but they are also highly optimized and compressed (more about map data format later). That single executable is also a standalone HTTP server. Its size is about 12MB, and it does not have external dependencies (except a few Linux standard shared libraries, of course).

The same Compact Maps executable runs out of the box on any Linux distribution having kernel version 3.2 or newer. The binary runs unchanged on x64 CPU under Debian, Gentoo, Ubuntu, Mint, Red Hat, CentOS, Fedora, etc. The ARM version of Compact Maps runs on any CPU with an instruction set compatible with ARM Cortex-A7, which, for all practical purposes, nowadays means any ARM processor. Yes, Compact Maps runs on Raspberry Pi 2.

vector map tiles

Performance and Footprint

Maps are stored in files, one file per country, in a highly compressed format. These are read-only files that contain all information required for map tile rendering, geocoding, and routing. The size of files is roughly three times smaller than the popular "mbtiles" format, which contains only map tiles data, without geocoding indices or routing data overlays.

For example, to turn any Linux box into a full-blown WEB map API service provider for European maps, you need one single executable and 47 map files, with a total size of about 10 GB. Performance? A single virtual AWS instance running on Intel(R) Xeon(R) Platinum 8124M CPU @ 3.00GHz with 16 GB RAM can handle up to 500.000.000 mixed tile/geocoding/routing requests monthly. This instance may generate about 300 (vector) tiles and calculate 50 routes per second at burst (1 - 300 km).

If your demand exceeds those numbers, you just need to clone the instance and put an HTTP load balancer (HAProxy, for example) in front of them both. Or make more replicas, should you need them, and scale the service indefinitely. Each Compact Maps instance is self-contained, and it does not communicate with other instances because there is no shared storage or any other shared resource among them. If you need to serve other WEB content from the Compact Maps instance and need more complex HTTP request parsing/rule matching, you may install Nginx and configure it to act as a reverse proxy for map requests.

Comparison with an open-source alternative

To put all of these into the perspective, let's compare Compact Maps with an open-source system that would provide similar functionality. We have to restrict to OpenStreetMaps (OSM) data since there are no open-source projects that deal with commercial map data (Compact Maps, on the other hand, can serve maps from OSM, HERE, TomTom, and myriad other map data providers). A popular choice for the OSM data-based WEB map services would be MapTiler + Nominatim + GraphHopper. MapTiler is a tile retrieval service, Nominatim is a geocoding (textual search) engine, and GraphHopper is a routing service.

MapTiler is the simplest one since it only fetches pre-generated vector map tiles from the SQLite database (mbtiles format). But, you have to pre-generate tiles in advance using some other tool and deal with large resulting SQLite database (~30 GB for OSM Europe). Textual address search provided by Nominatim is implemented within the PostgreSQL database with PostGIS extension. Nominatim imports OSM data into the PostgreSQL database once, creating appropriate database structures suitable for subsequent textual searches. The WEB service exposing geocoding functionality is then a mapping from WEB request to SQL procedure call written in PHP. Finally, GraphHopper is a routing engine written in Java that needs preprocessed map data optimized for its routing algorithm.

To create Compact Maps equivalent on a single server, you need MapTiler server that comes with NodeJS engine, huge PostgreSQL Nominatim database with PHP HTTP request mapper, and GraphHopper Java engine. Combining these three services into one means that you have to put HTTP reverse proxy in front of them (Nginx or Apache) and forward HTTP requests to the appropriate backend. To make things worse, data preprocessing time (tile generation, Nominatim import, and routing data preparation) is measured in days, not hours or minutes, in the case of European OSM maps.

Compact Maps provides all of the above in one single dependency-free binary. Let's see why and how, which is the story that covers 20 years of passionate programming and some engineering ingenuity.

The journey from cached PNG tiles to on-the-fly generated vector tiles

Mireo created its first WEB map in June 2005, roughly 5 months after Google launched their Maps. Google Maps were originally created by brothers Lars and Jens Rasmussen at Where 2 Technologies, and from many aspects, it was a breakthrough in both mapping and WEB programming. Mireo, on the other hand, created the first navigable digital map of Croatia, and once we saw Google Maps, we eagerly wanted to do the same for Croatia (at the first launch, Google Maps were covering USA territory only, using map data from NAVTEQ). Mireo's Croatian maps on the WEB were a huge success, and even today, Mireo is mostly known in Croatia for this map.

Back at that time WEB map was a patchwork of 256x256 PNG tiles pre-rendered on the server-side. Zoom levels were fixed, and each more detailed zoom level doubled the resolution from the previous one. Our first PNG map tiles were generated by Windows GDI API and served by IIS. We used Windows GDI since we've had a map rendering engine written for Windows CE - the most popular OS at that time for GPS car navigation boxes.

Switch to Linux (actually platform-independent) map rendering was enabled by the colossal work of late Maxim Shemenarev and his Anti-Grain Geometry library. AGG is a work of genius. We've learned from Maxim's library how to render anti-aliased roads, how to render complex polygons, the importance of L1 cache locality, and how to do all of these things as fast as possible. The result was astonishing - we've sped up map rendering by almost 10x compared to Windows GDI, and we've made it platform-independent.

A couple of years after we've launched the WEB map of Croatia, we've expanded the map coverage to the whole of Europe. Regardless of the PNG map rendering speedup we've achieved, the size of pre-rendered tiles exploded. The total size of all pre-generated 256x256 map tiles for Europe for all zoom levels was above 600 GB. When Steve Jobs introduced Retina Display with iPhone 4, the headache quadrupled - now we had to generate two sets of tiles, one set with 256x256 tiles and the other one with tiles of size 512x512. European maps' size grew to over 3.2 TB. That's hard to create, hard to transfer, and terribly difficult to update.

 

With the introduction of vector map tiles and the WebGL standard, things have changed. Vector tiles contain a much more compact geometry description of map objects than fully rendered PNG bitmaps. However, clients (WEB browsers) have to render map geometries on their own, which would be way too slow without a hardware-accelerated graphics engine. WebGL made that possible, and it even enabled attractive new features - map look and feel (style) may be dynamically changed, zoom levels do not need to be fixed anymore, and map can be rotated and tilted freely.

The AGG-like map rendering pipeline we've created earlier allowed us to easily change the output of the map rendering engine from PNG image to vector tile. PNG rendering pipeline looks like this:

fetch data → clip → project → render bitmap → save PNG

while vector tile generation pipeline has the form:

fetch data → clip → project → output to Protobuf

In other words, instead of rendering prepared geometry to PNG, the geometry and accompanying attributes are rendered into Protobuf format (the vector map tile Protobuf format was standardized by Mapbox.) Note that extracting vector tile from map database does not actually render anything; it just extracts map geometries and attributes of a small portion of the map and converts the data to Protobuf format. The GPU acceleration cannot be used here as no rendering is involved, and only the CPU may do the job.

When we started to generate vector files, we took the same approach as with PNG tiles, and we've pre-rendered all vector tiles on the server to be able to quickly fetch tiles directly from the disk upon request. It was already a huge saving - instead of 3.2 TB data for European PNG tiles, we had around 60 GB of vector tiles. That was 53x less space! Still, we wanted more.

Map data consists of road and polygon geometries, attributes, names, driving rules, signposts, and other stuff. Rendering a map is just one piece of work that the GPS navigation system does with the map data. Searching locations by name and calculating routes on the road network is another set of features that the navigation system has to deal with. Those other things require some unique indexing and routing graph overlay construction to be embedded within the map database. Mireo developed a long time ago a special, compact map data format that contains all the extra information that a GPS navigation system needs to run fast, even on a small ARM machine. As a ballpark figure, the size of maps of all European countries in Mireo format is about 10GB (that includes a large part of Russia and complete Turkey).

We use the same compact map database as the source of data on the server-side for vector tile generation. Now, instead of pre-generating all vector tiles at once and then serving just plain files from the WEB server, we wanted to extract vector tiles directly from our map format, thus reducing the storage size from 60GB to only 10GB in the European case.

And that's precisely where we ended up - by carefully implemented data transformation pipeline which heavily exploits CPU cache locality, shared-nothing architecture, and minimal re-allocation policy - we achieved the performance we wanted. The server creates an average 1024x1024 vector tile in about 4ms from our map data format, and that includes reading data from the disk, cropping map portion, and transforming the data to Protobuf format. Along the way, we've used some very heavy artillery like advanced C++20 features, Eric Niebler's range-v3 C++ library, which fits perfectly into the AGG pipeline, and pretty much everything we know about low-level programming.

Search for addresses or why OSM feels bad at geocoding

map search, geocoding and reverse geocoding

Geocoding is the process of converting the textual name of a geographical location to the corresponding longitude/latitude pair.  For example, geocoding converts the textual address "767 5th Ave, New York, NY 10153" to the longitude/latitude pair 73° 58' 22.76" W, 40° 45' 49.93" N (yes, that's the location of Apple Store).

At first glance, the geocoding algorithm does not look like a too big deal. All objects in the map database always have precise geographic coordinates, and their names are stored as simple textual attributes. Apart from the fact that maps tend to be big, the geocoding algorithm needs to find the object whose name attribute equals the input string and then return the matched object's coordinates.

Objects in the map, however, have topological properties which are not obvious. The Apple Store's address could have been written as "767 5th Ave, Manhattan" (actually, that's how locals would write the address). Manhattan is also a county of New York, a part of the metropolis New York, in the State of New York. When one writes "767 56h Ave, New York," to which of these "New York(s)" she/he was thinking of?

When people write a street address, they tend to use all sorts of ways to disambiguate between streets with the same name in different cities. However, the notion of a "city" here is often fuzzy and far from being unique. For example, there is another "5th Ave" street in Brooklyn, so is the address "5th Ave, New York" in Manhattan or Brooklyn?

Cities, towns, helmets, villages, counties, states, etc., may be considered as areas that somehow group geographical locations. There's also a hierarchy among areas - cities belong to counties, counties belong to states, and so on. We may also view ZIP codes as another sort of geographical area. People seldom use names from area hierarchy to describe more precise a street address. In our original example, we have 767 5th Ave (house number and street name), New York (metropolis), NY (state) 10153 (ZIP code). Obviously, 767 5th Ave, 10153 would have been enough to describe the location uniquely, but people add redundant information just in case. This kind of fuzziness is the first big challenge that geocoding algorithm has to deal with.

The second type of challenge arises from the fact that it is often not clear which part of address means what. Consider the location "Hotel Grand Paris." Is this the "Hotel Grand" in Paris or the hotel with the name "Grand Paris"?

Finally, when there are multiple string-equal matches, how geocoding algorithm may sort the results from most probable to least probable? What are the ingredients of the ranking? Should we also take into account the physical distance from the user's location to the result? For an input "London," is it always better to list "London, UK" first and then "London, Ohio?"

Most Nominatim OSM geocoding problems are the consequence of missing area hierarchy information in the OSM data. Some countries have better coverage, some have very poor, but as a result, the geocoder quality feels second-class. It is not the problem in the Nominatim's algorithm; it's a problem of the data. However, the problem may be circumvented if you use area information from external sources while strictly obeying local country rules. That's the approach we've taken in Compact Maps.

Without going into too many details, I'll mention that Compact Maps also uses a custom probabilistic string matching algorithm (BM25 will not work here, nor you can use Levenstein metric) to estimate the goodness of a string match. We use the entire area hierarchy to find possible matches. Finally, the sort by relevance of the resultset uses a formula obtained by machine-learning techniques using inputs from our GPS navigation users.

Routing

professional map routing

Route calculation determines a road path between origin and destination according to some optimality criteria. One may want to find the fastest, shortest, most eco-friendly, or a route with the smallest number of turns, and so on. A route should obey all traffic rules valid for a given vehicle type, so for example, passenger cars cannot drive one-way streets in the opposite directions, and heavy trucks cannot enter city centers.

Complimentary to route calculation, there's often a need to attribute turns along the way with navigation guidance. Navigation-enabled clients use guidance instructions when navigating in real-time, while routing planners typically allow users to view or print all turn steps along the route.

 

Routing engine implementation is the most challenging of all GIS algorithms. A real-world routing engine must:

  • have reasonable performance and resource usage
  • ensure correctness
  • support one-off and dynamic changes of optimality goals

Interestingly enough, there were no significant improvements in street network routing algorithms from 1959 and the original Dijkstra's invention until 2006. Partially motivated by DIMACS Challenge 06, researchers from the University of Karlsruhe made the real breakthrough in 2007 with various types of mathematically correct "hierarchical" routing. Their Transit-Node routing algorithm, the DIMACS Challenge winner, was roughly 3,000,000 faster than the original Dijkstra's. Contraction Hierarchies (CH), another routing algorithm from the same group of researchers, is probably the most widely used today in commercial and open-source cloud systems.

We've started to implement the CH algorithm (mobile variant) in 2008, and it took us three years to get to the production-ready stage. Like any other algorithm that effectively pre-calculates routes during the preprocessing phase, the CH  has a drawback that dynamic changes to the routing graph are difficult to apply. Professional navigation systems must take live traffic information into account, and thus mutating the routing overlay graph is necessary. But we managed to do it. Surprisingly, to the best of our knowledge, Mireo's embedded navigation system is, 12 years later, the only offline professional GPS navigation that uses a CH-like routing engine.

Mireo's implementation calculates a 3000 km route across the continent on an ARM-based embedded machine in 800ms. Compact Maps use exactly the same routing engine on server hardware, where we achieve the performance of about 50 mixed short to long routes per second. These routes take live traffic into account, they are mathematically optimal, and guidance attributes are included.

20 years of passion is what matters the most here

As noted in the introduction, Mireo Compact Maps is functionally equivalent to the open-source suite MapTiler + Nominatim + GraphHopper. The complete Compact Maps functionality is contained in a single, 12 MB dependency-free Linux executable. But, Compact Maps are not only functionally equivalent; they are built on years of Mireo's experience creating professional GPS navigation products for commercial vehicles. The requirements and standards of the car industry forced us to smooth down all rough edges of mapping algorithms, adapt services to all country-specific rules, and make the system run smoothly on ARM7 CPU with 64MB RAM (that's indeed MB, not GB).

Experience is what matters the most. It is hard to forget the Apple map fiasco when they introduced iOS 6 in 2012 and Apple Maps along with it. Although Apple certainly can hire the best men for the task, the fail was epic. It took Apple almost two years to polish the Maps to an acceptable level. Apple's fail is clear proof that to build a professional mapping product, a company needs even more focus and time than the usual relentless attention to details that Apple typically puts into their products.

That's what we were doing for the last 20 years.