MaMa (short for Map Matcher) is a library that lets you perform real-time map matching of locations coming from multiple clients as part of distributed system (but in its core it is just a library which can easily be used locally). Main target of MaMa is blazingly fast performance.
Here is example how one can configure and run mama
map matching service for Berlin:
mkdir tiles
cd tiles
# download OSM data
wget http://download.geofabrik.de/europe/germany/berlin-latest.osm.pbf
# generate mama tiles
docker run -t -v $(pwd):/tiles ghcr.io/siarheifedartsou/mama:main tilegen /tiles/berlin-latest.osm.pbf /tiles
# run mama-server
docker run -t -p 50051:50051 -v $(pwd):/tiles ghcr.io/siarheifedartsou/mama:main mama_server /tiles
This service exposes API via gRPC, so you have to use gRPC client to access it(see mama.proto for service definition). For test purposes it can be done with grpcurl
:
docker run --add-host host.docker.internal:host-gateway fullstorydev/grpcurl \
-plaintext \
-d '{"entries": [{"location": {"latitude": 52.517037, "longitude": 13.388860, "timestamp": "2023-01-01T00:00:00Z"}}]}' \
host.docker.internal:50051 \
mama.server.api.MamaService.Match
It should output something like:
{
"entries": [
{
"location": {
"timestamp": "2023-01-01T00:00:00Z",
"latitude": 52.51703335973838,
"longitude": 13.38879800553748,
"bearing": 354.47464844888776
},
"state": "ChYKDwoICMfC ggQsk4VYb4bPxXuZgi/ChYKDwoICMfC ggQ6U8V5TLCPhXuZgi/ChYKDwoICMfC ggQsk4V/xUHPxVdNkK/ChYKDwoICMfC ggQ6U8VqYPrPhVdNkK/ChYKDwoICMfC ggQojAVfiZuPxXDgaDAChYKDwoICMfC ggQ60MVwmd9PxWFtLDAChEKCgoICMfC ggQ508VhbSwwAoRCgoKCAjHwvoIEOhPFYW0sMAKFgoPCggIx8L6CBCiMBUm40c/FSLD48AKFgoPCggIx8L6CBCiMBWosi0/FSi1L8EKFgoPCggIx8L6CBDoTxXF60Q FV6MQMEKFgoPCggIx8L6CBCxThVt/oM9FUrOSMEKFgoPCggIx8L6CBCQQRWYL38/FSnjVcEKFgoPCggIx8L6CBCuThWX9H4/FSnjVcEKEQoKCggIx8L6CBCwThUp41XBChYKDwoICMfC ggQsU4V 4wXPhX5yV7BChYKDwoICMfC ggQ60MVrQc9PxVh8pDBChYKDwoICMfC ggQ508VKcCAPhVh8pDBEhoKBgiAmsOdBhE26bZELkJKQBnzcW2oGMcqQBolCgYIgJrDnQYROIItJi5CSkAZJxE9iBDHKkAiCQkf0fgomCd2QA=="
}
]
}
Note state
field, it encodes map matching state for particular vehicle. You can pass this state field in subsequent requests to take advantage of the knowledge of past vehicle locations:
docker run --add-host host.docker.internal:host-gateway fullstorydev/grpcurl \
-plaintext \
-d '{"entries": [{"state": "ChYKDwoICMfC ggQsk4VYb4bPxXuZgi/ChYKDwoICMfC ggQ6U8V5TLCPhXuZgi/ChYKDwoICMfC ggQsk4V/xUHPxVdNkK/ChYKDwoICMfC ggQ6U8VqYPrPhVdNkK/ChYKDwoICMfC ggQojAVfiZuPxXDgaDAChYKDwoICMfC ggQ60MVwmd9PxWFtLDAChEKCgoICMfC ggQ508VhbSwwAoRCgoKCAjHwvoIEOhPFYW0sMAKFgoPCggIx8L6CBCiMBUm40c/FSLD48AKFgoPCggIx8L6CBCiMBWosi0/FSi1L8EKFgoPCggIx8L6CBDoTxXF60Q FV6MQMEKFgoPCggIx8L6CBCxThVt/oM9FUrOSMEKFgoPCggIx8L6CBCQQRWYL38/FSnjVcEKFgoPCggIx8L6CBCuThWX9H4/FSnjVcEKEQoKCggIx8L6CBCwThUp41XBChYKDwoICMfC ggQsU4V 4wXPhX5yV7BChYKDwoICMfC ggQ60MVrQc9PxVh8pDBChYKDwoICMfC ggQ508VKcCAPhVh8pDBEhoKBgiAmsOdBhE26bZELkJKQBnzcW2oGMcqQBolCgYIgJrDnQYROIItJi5CSkAZJxE9iBDHKkAiCQkf0fgomCd2QA==", "location": {"latitude": 52.517301, "longitude": 13.38884, "timestamp": "2023-01-01T00:00:03Z"}}]}' \
host.docker.internal:50051 \
mama.server.api.MamaService.Match
See our demo for example of real life usage.
In order to work mama
preprocess OSM data to more convenient representation. tilegen
is a tool used for that.
tilegen
takes .osm.pbf
as input and slices it to tiles. Tile scheme corresponds to level 11 of S2Geometry, i.e. has approximately 20 km^2 in area:
Each tile stores metadata about road graph edges accessible by cars in particular area and S2 index which allows to effectively find projections on road graph.
tilegen
also optionally precomputes shortest paths used in map matching algorithm, which significantly boosts runtime performance.
libmama
is C library implementing core features of mama
. mama_server
can be a good example of how it should be used.
mama_server
is gRPC service which wraps libmama
and provides map matching capabilities to external clients. This service doesn't store any state and it is responsibility of clients to store map matching states(see demo for example how Redis can be used for that purpose).
- Map matching algorithm itself is mainly inspired by "classic" Microsoft paper
Hidden Markov Map Matching Through Noise and Sparseness
. - Shortest paths precomputation is inspired by
Fast map matching, an algorithm integrating hidden Markov model with precomputation
paper.
MaMa uses MIT license.