DMM: A distributed map-matching algorithm using the MapReduce paradigm

Map-matching is the problem consisting of matching a sequence of geographic coordinates with the roads on a digital map, aiming to discover the actual path traveled by that trajectory. Common uses of map-matching include traffic analysis and flow density extraction, which rely on such algorithms as a primary stage of their processing. Here we present DMM, a distributed solution for large-scale trajectory data processing and suitable for low-sampling-rate GPS trajectories. This solution is based on another low-sampling algorithm [1], and adapted to work in a distributed manner, using the MapReduce paradigm. For this purpose, we heavily rely on the Apache Spark framework and its data abstraction, Resilient Distributed Datasets (RDDs). The experiments show that the DMM algorithm has high accuracy and scalability and can be used for trajectory data streams.