Efficient and fast map matching with Valhalla

5 minute read

Published:

[Updated on 14.09.2022] [Updated on 04.07.2022]

The Valhalla (documentation, source code) is a fast, efficient, multimodal and open-source routing service that is being used by many mapping and routing giants. The engine provides an easy-to-use interface to use OpenStreetMap (OSM) data for routing purposes. Instead of talking about the routing engine, my focus is on map-matching which is one of the many APIs offered within the Valhalla.

Map matching

As the name suggest, map-matching is a process to associate geographical coordinates to a digital map (More info on Wikipedia). In this case, our task is to match the bicycle tracks data to the map. The map-matching API in Valhalla is called Meili. A great tutorial that focuses on Meili can be found here. In this post, my target is to document the entire process from setting up a Valhalla server to using it in Python.

  1. As usual, the docker solution is the preferred one which avoids the installation of libraries on a local machine thereby providing an OS-independent solution. I found the docker image form gis-ops as a good starting point. If you are on Windows, then try using PowerShell, because git-bash behaves strangely with volume mounting.

  2. Pull the prebuild docker image and start the server. In case, if we need to build from the source, then documentation is here.

    1. Pull the docker images from GitHub. For the same, you might need to login with your GitHub’s credentials.
      docker login docker.pkg.github.com
  docker pull docker.pkg.github.com/gis-ops/docker-valhalla/valhalla:latest
    1. We will mount the local folder to the drive. Therefore, create a folder called custom_files and download the OSM data from the generous server of geofabrik as:
          cd custom_files
      wget http://download.geofabrik.de/europe/germany/baden-wuerttemberg-latest.osm.pbf

    The above download part can be skipped and can be coupled directly during the docker run but for simplicity, I downloaded it here.

    1. Then, we can turn on the server for Valhalla. Below, we define a local volume to mount i.e. where we will provide the OSM extracts and this folder is linked to the docker server (-v option). Various options can be found here which can be passed to Docker via -e flag. In the following, I only use build_admins which will also create a database for the countries and states. Then, I also set serve_tiles as True which will first build the map tiles from the mounted $PWD\custom_files and then directly start serving. This is different compared to the older version of this docker image.
         docker run -dt -p 8002:8002 -v $PWD\custom_files:/custom_files/ -e serve_tiles=True  -e build_admins=True  docker.pkg.github.com/gis-ops/docker-valhalla/valhalla:latest
    1. [Optional] In the above, we’ve used the -d option for the silent operation. So, during the trial phase, we can see the logs with standard docker commands. First, find the running container id and then follow its log.
         docker ps
     docker container logs -f <CONTAINER_ID_OBTAINED_FROM_ABOVE>

    1. For the downloaded ~500 MB OSM extract, it took around 30 minutes. Otherwise, you can start with smaller extracts, SSD drive is recommended for regular builds or larger file sizes. Once the graph build is finished, you will observe some output like INFO: Finished tarring 110 tiles to /custom_files/valhalla_tiles.tar. Thereby, you will also see a valhalla_tiles.tar file which has the optimized graph.

    2. Check the running container by docker ps, and you should be able to see the docker status and opened port which is 8002.

  3. Now, we are good to go to use the server. To test whether the server is running:
    1. We could try http://localhost:8002/ in the browser. We should see "error_code":106. It indicates that the server is running but we did not pass any specific API address and we could see available end points.
    2. As a tar file is available due the map build process in custom_files folders, so we could query this data with the help of curl in our terminal.
     curl http://localhost:8002/route --data '{"locations":[{"lat":48.632608,"lon":9.010350,"type":"break"},{"lat":48.631776,"lon":9.011528,"type":"break"}],"costing":"auto","directions_options":{"units":"miles"}}' | jq '.'

  4. We can take the inspiration from the already mentioned blog to automatize things in Python.

  5. Finally, you can find a complete notebook alongside a sample gpx trace on my GitHub, which illustrates the map matching with figures. To use this, you need to start Valhalla’s server as mentioned above for the Baden-Wuerttemberg state in Germany because the attached GPX traces are from this state.

It is worth mentioning that default settings allow you to perform a map-matching to ~200 KM. To surpass this limit, you need to change the settings in valhalla.json in your custom_files folder and restart the docker.

How much time to build for entire planet?

The answer depends heavily on the underlying hardware one is using. On a system with 16 GB RAM and 1 TB of HDD hard disc, the process went on for more than 12 days and then ultimately I aborted the process. Building the tiles is a computationally expensive process, therefore, always use the SSD for large areas as it will make IO very fast and this appears to be a bottleneck in this operation. Additionally, keep around 600 GB of space, even though the final tar file will be of much less size. This is required because program write down many temporary files during the graph building process. This space requirement will grow significantly if you also want to have elevation tiles, as elevation only can take up to 1.6 TB of space. On a good system equipped with SSD, 8 cores and 16 GB of RAM, it took around 2.5 days. For entire 1 day, I can see 100% of CPU was used, so I assume that the build time can build down further if we use more cores. If you don’t have the resources, and then you can also buy the tiles, but it’s a bit expensive in my opinion because of the subscription model.

Reach out to me on Instagram for a faster reply! "Buy Me A Coffee"

You May Also Enjoy

Setting up an Overpass API server with Docker

3 minute read

Published:

You might have already seen my blog on OpenStreetMap from 2020. In that post, I briefly talked about Overpass API server with a pointer to a GitHub repo to setting up locally. However, that setup might fail if we try to build for entire planet. Additionally, source repository hasn’t been updated for 5 years. I’ve received some requests to assist in setting up the Overpass server. Therefore, this short post basically illustrates the process of local Overpass server.

Starting your own Overpass API server

Currently, the process has been very simple and straightforward, thanks to this docker image docker image.

Building the server from raw OSM files

This approach is beneficial when our region of interest in small (compared to entire world).

docker run -e OVERPASS_META=yes -e OVERPASS_MODE=init -e OVERPASS_PLANET_URL=http://download.geofabrik.de/europe/monaco-latest.osm.bz2 -e OVERPASS_DIFF_URL=http://download.openstreetmap.fr/replication/europe/monaco/minute/ -e OVERPASS_RULES_LOAD=10 -v /overpass_db/:/db/overpass_clone_db -p 8888:80 -it --name overpass_monaco wiktorn/overpass-api

This usually takes 5 minutes on a normal computer including the downloading image from dockerhub, downloading OSM file from geofabrik and building the database for a 700 KB file. All the generated builds can be used with the server. At the end of this build, docker container will be stopped and need to be started again. For the same, either one can assign a name to container in the previous step or can look at auto-generated name with docker ps --all command. After grabbing the name, simply start the container as docker start <CONTAINER NAME>. Alternatively, one can pass -e OVERPASS_STOP_AFTER_INIT false option so that we can continue the instance after flushing database.

img

With that, we can query for a pizza shop: -.

In the above, we didn’t use a custom region as shown here obtained from OSM tool without tweaks. But, workaround should be simple, i.e. either providing file as file:/// as mention here or hosting file with local HTTP server.

Note: So far, I am not able to circumvent the issue when I try to mount a local folder in current directory. Although build was successful however during the query server results in error. This is specific to windows only.

Cloning for entire world

When we need to scale up to entire world, then cloning is a better option compared to building from the raw OSM file. In this case, we can pass the option in OVERPASS_MODE for clone. The data will be cloned from the Overpass API server with the defined replication. You can check out available replication frequency on the OSM wiki.

docker run -e OVERPASS_MODE=clone -e OVERPASS_DIFF_URL=https://planet.openstreetmap.org/replication/day/ -v /big/docker/overpass_clone_db/:/db -p 8888:80 -it --name overpass_world wiktorn/overpass-api

This process took approx 2 hours with a good internet speed on a Linux machine, and it took approx 204 GB. For sure, this number will grow with more contributions. We can now query for nearby Indian restaurants from our POI with query: -

Using in Python

I have a sample REST API with Flask which basically finds the nearest toilets from the query point. To use the above server is easy, we just need to change the URL of Overpass API server mentioned here to self.sever = 'http://localhost:8888/api/interpreter'.

Reach out to me on Instagram for a faster reply! "Buy Me A Coffee"

Machine Learning Applied to Stock Market Prediction: A Comparison between LSTM and ESN

5 minute read

Published:

I have been working with various neural networks for a while and always find recurrent neural network (RNN) very special. Whenever, there is a dependency with previous data points, then these networks shines out. Time-series problem especially fits here for e.g. predicting the weather pattern or stock market. In the past, I have done work to compare various RNNs for such tasks and my work concluded that ESN works quite well compared to simple deep neural network and some RNNs like LSTM or GRU (paper-1, paper-2 and paper-3) (of course this statement vary with the domain). Those works were done mostly with the scientific data for turbulent flow for thermal plumes, which has significant effects on weather (Wikipedia). Now, I was curious to see how these network can work for practical purpose.

Deep learning on HPC cluster with LSF queue

2 minute read

Published:

This is rather a short documentation to run the TensorFlow jobs on a high performance computing (HPC) cluster which is using LSF Load Sharing Facility. This can be extrapolated to other HPC systems with some tweaks. If you’re new to LSF and HPC jobs with DL then this post nicely summerizes the jargon.