BMW CarIT Logo Typo

Blog

News, ideas and events

Blog

Announcement: Barefoot release – Online map matching with real-time visualization using NodeJS and OpenLayers

In the last weeks, I noticed a significant increase of interest in our Barefoot library due to a viral spreading on Twitter. I’m very happy about the attention and positive feedback. I would like to grasp the opportunity and the attention for announcing some features that will be available with the next release, which will be published within next weeks.

In the next release, Barefoot’s online (real-time) map matching will be outfitted with a tracker server that matches streams of JSON position messages in real-time to keep track of moving objects. It pushes map matched tracks to Barefoot’s monitor server, which consists of a NodeJS backend (Express and Socket.io) and a JavaScript frontend (OpenLayers), for visualizing map-matched tracks on the map of OpenStreetMap in real-time, see Figure 1.

Figure 1: Barefoot's tracker server matches streams of position messages in real-time and pushes map-matched tracks to Barefoot's monitor server, which consists of a NodeJS backend (Express and Socket.io) and a JavaScript frontend (OpenLayers) for visualizing the tracks on the map.

Figure 1: Barefoot’s tracker server matches streams of position messages in real-time and pushes map-matched tracks to Barefoot’s monitor server, which consists of a NodeJS backend (Express and Socket.io) and a JavaScript frontend (OpenLayers) for visualizing the tracks on the map.

A web-based frontend shows objects with map matched positions (red) and – when hovering with the mouse cursor – also the map matched paths (red), see video below. Selecting an object focuses on the object and shows the full result of Hidden Markov Model map matching [1,2], which includes alternative positions and paths (green) with their probability (indicated by transparency). This may not only be an interesting use case for businesses and Open Source and Open Data projects, but also illustrates the essence of Hidden Markov Model map matching: It keeps track of alternative positions and paths, rates them with a probability, and converges with each iteration for increasing confidence on the object’s position and path on the map.

Barefoot's tracker and monitor server are started from command-line and provide a real-time web-based visualization of map matched tracks on the map. A stream of position messages is simulated with a simple script, and is then map matched and visualized in real-time. The example shows a border case of real-time map matching where an object is moving on a road that is close to another parallel road. It keeps both paths as hypotheses with approximately equal weight and finds the object's correct path and position eventually.

A single machine (commodity hardware) can host Barefoot’s tracker and monitor server for handling hundreds of objects, each sending position update messages every second. A large scale solution of Barefoot’s tracker server for handling several thousands (or maybe millions) of objects is straight-forward. (Here, we do not focus on scaling Barefoot’s monitor server.) A simple state-of-the-art solution uses a combination of Storm, Kafka, and Cassandra (see Figure 2): [3]

Figure 2: Scaling out Barefoot's tracker server with Storm for matching streams of position messages from a large number of objects in real-time; where messages are pulled from Kafka and object states are stored in Cassandra with the object's map-matched position and path.

Figure 2: Scaling out Barefoot’s tracker server with Storm for matching streams of position messages from a large number of objects in real-time; where messages are pulled from Kafka and object states are stored in Cassandra with the object’s map-matched position and path.

  • Streams of position messages, each sent from a moving object, are queued in Kafka which acts as a partitioned and distributed message queue.
  • Storm pulls position messages from Kafka (blue arrow) and determines each object’s state, consisting of its position and path on the map. For that purpose, it performs map matching of position messages in real-time and keeps track of the objects’ states.
  • Object states are stored in Cassandra which is a distributed hash table that enables fast reading and writing (red arrows) and provides a HDFS interface for further processing with Hadoop.

With each position message, Storm must read the state of a respective object from Cassandra to perform map matching. However, remote reading from Cassandra induces higher latencies during processing. To decrease latency, Storm nodes may try avoiding reads (dashed red arrow) by caching object states in local memory. As a consequence, Storm must assign position messages to nodes holding the respective object’s state in cache (dashed blue arrows). For that purpose, Storm nodes must divide the set of object states into subsets A, B, C … (e.g., ranges of object ids or geographical regions) and must forward messages to the appropriate node if necessary. Message forwarding can be implemented easily with Storm’s concept of direct stream grouping and can be coordinated with Zookeeper. Only if the object’s state is not in local cache, e.g. if an object moves to another region, a Storm node must read the state from Cassandra.

As maintainer of the project, I’m inviting enthusiasts and experts to join the project and to use Barefoot. – It’s free and uses free map data, thanks to OpenStreetMap. – Making Barefoot a part of the Open Source community in Geographic Information Systems may not only support your business but also helps other great Open Source and Open Data projects, such as OpenStreetMap.

References

[1] P. Newson and J. Krumm. Hidden Markov Map Matching Through Noise and Sparseness. In Proceedings of International Conference on Advances in Geographic Information Systems, 2009.

[2] C.Y. Goh, J. Dauwels, N. Mitrovic, M.T. Asif, A. Oran, and P. Jaillet. Online map-matching based on Hidden Markov model for real-time traffic sensing applications. In International IEEE Conference on Intelligent Transportation Systems, 2012.

[3] S. Mattheis, K. Al-Zahid, B. Engelmann, A. Hildisch, S. Holder, O. Lazarevych, D. Mohr, F. Sedlmeier, and R. Zinck. Putting the car on the map: A scalable map matching system for the Open Source Community. In INFORMATIK 2014: Workshop Automotive Software Engineering, 2014.