Systematic identification and analysis of map-matching anomalies in road network models for urban cycling

Objectives

We aim to study the challenges emerging from the existence of gaps between real cycling traces and their representation in OSM. We defined the following two objectives:

• O1: Develop an unsupervised computational method to process sets of cycling traces and identify city areas prone to map-matching anomalies.

Analysing map-matching anomalies can help municipalities and OSM collaborators detect areas where the reality of cycling traces systematically diverges from the matching of those traces into the road network data model. Knowledge about these anomalies may help them identify opportunities for improvement. These improvements may include changes in OSM representation of cycling routes, suggestions for infrastructural changes, or even tips for cyclists. This contribution may help improve future cycling applications, generate better route suggestions, and produce novel insights about cycling behaviour. It is important to note that the method proposed in this study should be independent of the specifics of the map-matching algorithm used.

Paper structure

The article is structured as follows: The next section reviews the current state of the art. Section “Methodology” describes the overall methodology for identifying map-matching anomalies, and section “Step description and results” details each step and presents the results of applying this methodology to a real dataset. The subsquent section discusses how overcoming anomalies can enhance cycling conditions. Finally, the “Conclusions” Section summarises the main findings and outlines potential directions for future research.

OSM road network completeness

The popularity and widespread use of OSM have led many authors to assess the quality and completeness of OSM data. Overall, studies have shown that OSM data has relatively good quality and particularly high quality for designated lanes (Hochmair et al., 2015). In some cases, it is even more complete than official datasets (Ferster et al., 2020), as informal paths and new infrastructures are often mapped in OSM before they are released on official datasets (Nelson et al., 2021). Comparing OSM to reference datasets, roads tagged as ‘on-street bicycle lanes’ appear the most concordant, while cycle tracks and local street cycleways appear the least concordant (Ferster et al., 2020).

Globally, OSM is found to be 83% complete, and in 40% of the countries, it covers more than 95% of the roads (Barrington-Leigh and Millard-Ball, 2017). OSM is found to be a reliable tool for many applications, for example, for computing the Level of Traffic Stress metric (Wasserman et al., 2019) and for vehicle routing applications (Graser et al., 2015). However, Viero et al. stated that OSM has insufficient quality for performing network-based analysis of cycling conditions (Vierø et al., 2024).

Despite its good quality, Hochmair et al. (2015) identified two common types of errors, namely, omission and commission. Omission errors occur when a cycle lane is not represented in the OSM or misses proper tags, while commission errors occur when OSM includes non-existent roads or roads with incorrect geometries or tags. Due to its crowdsourced nature, a key challenge is to achieve consistent OSM tagging. Not all mappers have sufficient training in geography and surveying, and those who do might often employ diverse labelling practices, leading to inaccurate, incomplete, inconsistent, or vague contributions (Basiri et al., 2016; Ferster et al., 2020; Nelson et al., 2021). Some street typologies and urban contexts are more prone to errors. Completeness has a U-shaped relationship with population density; both sparsely populated areas and dense cities seem to be the best mapped (Barrington-Leigh and Millard-Ball, 2017).

Map-matching

Map-matching is a key process in modelling mobility. Given a road network model and a GPS trajectory of a vehicle, it tries to find the most probable sequence of road network edges on which the vehicle has travelled (Yang and Gidófalvi, 2018). However, applying map-matching for cyclists traces is particularly challenging, as cyclists frequently use paths that are not designed for cycling or that might not be included in the road network data, such as parks or shortcuts (Berjisian and Bigazzi, 2023; Schweizer et al., 2016). The built environment also influences the performance of map-matching algorithms. In areas with a complex road network, the probability of having map-matching anomalies is higher than in zones with a sparser road network (Trogh et al., 2022).

Several authors have targeted these challenges and proposed new map-matching algorithms specifically designed for cycling mobility. Schweizer et al. (2016) proposed a method that uses network attributes to estimate the route in case of incomplete GPS data and can identify if cyclists used a reserved bikeway. There also methods that favour bikeways extracted from OSM (Bergman and Oksanen, 2016), while others discard some roads depending on the transportation mode (Trogh et al., 2022). The method proposed by Gao et al. (2024) classifies road availability for cyclists to help during the map-matching process.

Some authors acknowledge the incompleteness of road network data and propose approaches capable of performing off-road map-matching or detecting road network errors. Murphy et al. (2019) proposed a method that generates and uses off-road trajectories as a fallback when the road network cannot accommodate the vehicle trajectory. Behr et al. (2021) proposed a method that extends the road network data model by triangulating all open areas and adding tessellation edges and considers each GPS point as a possible matching candidate, adding them to the road network graph if no match is found. Yang et al. (2024) used a neural network model to detect various categories of road network errors using extracted context features from the map-matching outputs, raw trajectories, and road network.

The off-road sections can then be used to interpolate missing road segments and to update the road network (Sasaki et al., 2019; Shan et al., 2015). The authors assume that, since vehicles are usually restricted to the road network, unmatched trajectories can be used to find new roads (Tang et al., 2019). Although this approach is reliable for cars, cyclists’ paths may correspond to illegal roads or connections and thus may not be eligible to be represented in a road network. OSM collaborators often follow the on-the-ground mapping rule, which states that the world should be mapped as it is physically observed (OSM, 2025).

In a different approach, some authors have studied the identification and characterisation of map-matching errors. Berjisian and Bigazzi (2023) used several similarity measures to compare the GPS trace with the map-matching output and flag cases requiring visual inspection. Dey et al. (2022) proposed a two-phase methodology that uses an unsupervised learning model to help classify map-matched segments as good or bad based on the quality of GPS points and uses the ‘edit distance’ metric to detect unrealistic travel behaviour. Carvalho et al. (2024) combined supervised machine learning with similarity measures to detect and classify gaps between GPS traces and map-matched routes.

In this work, we explore this problem in further detail and extract the exact portions of a GPS trace leading to map-matching gaps. Compared to our previous work, as described in (Carvalho et al., 2024), we shifted from a broad identification of gaps to a more specific identification of where exactly the gaps happen within the GPS trace. By applying this process to a large dataset, we remove the influence of sporadic events and identify which zones in a city are prone to anomalies. We do not assume that all gaps occur only due to road network or GPS errors but also due to cyclists’ habits or even internal map-matching errors.

Map-matching

In the map-matching step, we applied a map-matching algorithm to align the eligible GPS traces to the OSM road network. For this purpose, we used the map-matching service developed by Mapbox, which is a reference solution in this domain and supports OSM road network data models. We configured the map-matching service to consider the bicycle profile, which is described to avoid highways and give preference to streets with bike lanes. It is worth stressing that our work is not about the quality of map-matching algorithms. We are specifically looking for map-matching anomalies. While our results could be slightly different using other map-matching tools or by different map-matching parameterisation, our map-matching anomaly concept is inherent to the road network data models and therefore should be largely independent from the specifics of any map-matching algorithm. In the case of map-matching parameterisation, such flexibility is expected. Regions may have different rules for similar scenarios. For example, in some regions, cyclists may be allowed to ride against traffic, whereas in others such behaviour is prohibited. Thus, what may constitute an anomaly may vary across regions, and the anomaly identification process should be adaptable to these perspectives.

The Mapbox map-matching API ² accepts a sequence of 2 to 100 GPS coordinates as input, and the response of a map-matching request will fall into one of the following 3 categories:

(i) Map-matching error: The GPS trace could not be map-matched into the OSM road network. The result is an execution error, and no route is returned.

To ensure optimal results in the map-matching process, we preprocessed the 16,746 eligible GPS traces to ensure that consecutive GPS coordinates were at least 10 m apart. Additionally, due to the GPS coordinate limit per request, eligible GPS traces exceeding this limit were divided into segments of 100 points each, with the last segment potentially containing fewer points.

Results: This optimisation produced 43,761 segments, each corresponding to a map-matching request. Of those requests, 320 resulted in map-matching errors (e.g. an execution error where no route was returned), 37,998 resulted in one map-matched polyline, and 5443 resulted in multiple map-matched polylines. Table 2 resumes the results of applying the map-matching procedure.

OPEN IN VIEWER

Table 2.

The results of applying the map-matching procedure.

Description	Count	%
Eligible GPS traces after splitting	16,746	—
Total map-matching requests	43,761	—
Map-match: Error	320	0.7
Map-match: One polyline	37,998	86.8
Map-match: Multiple polylines	5443	12.4

Gap extraction

The gap extraction step aims to identify and extract the map-matching gaps. Cases where map-matching failed to produce any match were straightforwardly considered as a map-matching gap. The main challenge is to define rigorous criteria to identify gaps corresponding to routes that misrepresent the source trace. To address this challenge, in the cases where the map-matching produced one or multiple map-matched polylines, we used the Dynamic Time Warping (DTW) algorithm (Müller 2007) and the Optimal Warping Path (OWP) to compare the GPS trace with its corresponding map-matching polyline and identify the segments of both geometries that are below a certain level of similarity. DTW is a technique to find the optimal alignment between two sequences (time series) (Müller, 2007) and is widely used in different fields, such as speech recognition, trajectory similarity (Tao et al., 2021), and dynamic signature verification (Jiang et al., 2022). For two sequences, the DTW value is well-defined; however, they can have different warping paths. The OWP is a path that optimises the sum of all local distances. A local distance refers to the distance between two elements of each sequence based on a cost function. The cost function can be defined according to the purpose of the study. In our study, the sequences are composed of WGS84 coordinates. Therefore, we used the Haversine distance formula as the cost function.

It is important to note that before computing the DTW, we interpolated points every 2 m in the GPS and map-matched geometries. This solution reduced the impact of long intervals between consecutive points, which would lead to high local distances during the OWP computation, even when both geometries appear similar.

After computing the OWP, we classified map-matching gaps as corresponding to cases where the local distance was higher than 10 m for at least five consecutive points. Where a map-matching gap was detected, we registered the gap segment and its gap trace. The former corresponds to segments in the map-matching response, and the latter corresponds to the part of the source GPS trace that produced the gap.

Results: In total, we extracted 153,170 map-matching gaps. Figure 4 presents 2 examples of those gaps. The red dotted line represents the gap trace, while the blue represents the gap segment.

OPEN IN VIEWER

Figure 4.

Example of two different map-matching gaps detected.

Figure 4(a) illustrates a scenario where the cyclist used a ramp not mapped in OSM to transition from a cycleway to a residential road. The map-matching algorithm attempted to find a path connecting the cycleway and the residential road. Figure 4(b) shows a situation where the cyclist crossed the road outside the designated area. The map-matching algorithm snapped the GPS trace to the nearest zebra crossing.

Gap filtering

A large number of the map-matching gaps produced in the previous step correspond to very short route segments. To focus on an aggregate perspective and avoid many false positives, we decided to remove gaps where the gap traces were shorter than 40 m or where the ratio between the length of the gap trace and the gap segment was between 0.7 and 1.3. We consider false positives the case in which the map-matching algorithm successfully snapped the GPS into the correct road, but GPS interferences created a deviation in the GPS trace sufficient to induce our algorithm to consider it as a gap.

We also removed gaps where the gap trace consisted of the beginning or end sections of the GPS trace. These sections can easily lead to map-matching errors due to the calibration of the GPS sensor or the map-matching algorithm itself. While GPS problems could be addressed in the data-cleaning step, the interferences from map-matching calibration can only be detected in this phase.

Results: After the filtering procedure, we ended up with 29,151 eligible map-matching gaps. Table 3 summarises the results of applying the gap extraction and filtering procedure.

OPEN IN VIEWER

Table 3.

The results of applying the gap extraction procedure.

Description	Count	%
Total map-matching requests	43,761	—
Total map-matching gaps	153,170	—
Eligible map-matching gaps	29,151	19.0

During our analysis, we observed that most gaps with a ratio greater than 1.3 were removed, as they involved the beginning or end sections of the GPS traces.

Anomaly identification

In the anomaly identification step, we aimed to identify locations where gaps concentrate. The goal is to create an aggregate view of these gaps, focussing on their quantitative relevance, especially on truly systematic cases, indicating an underlying problem. A large cluster may not only be large due to having many gaps but also because it aggregates several smaller clusters that, despite having different characteristics such as movement patterns, share the same underlying cause. For this purpose, we applied the DBSCAN ³ clustering algorithm. To apply this procedure, we selected the midpoint in each gap trace since the midpoints of gaps passing through the same area tend to converge to the same location.

The rationale behind this procedure is that in zones where the road network does not represent the cyclists’ paths, map-matching is likely to produce recurring gaps, leading to areas with a high concentration of gaps. In contrast, sporadic events, such as strong GPS interferences or map-matching malfunctions, mainly result in spatially dispersed gaps. As DBSCAN groups data points based on spatial proximity, it mitigates the impact of sporadic events and highlights the most common gaps.

DBSCAN requires two parameters: the minimal number of points composing a cluster and the distance threshold (epsilon). After some experimental iterations, we selected a fixed epsilon of 15 m and a minimum number of 20 points. However, the optimal value for these parameters may vary depending on the number of gaps extracted, especially the minimum number of points. As the number of gaps increases, the minimum point threshold should be adjusted accordingly to prevent the formation of overly large and dispersed clusters.

Results: Table 4 shows the results of applying DBSCAN. In total, using the 29,151 eligible map-matching gaps, DBSCAN formed 157 clusters. In other words, it identified 157 anomalies. The clustering step excluded a total of 14,121 gaps.

OPEN IN VIEWER

Table 4.

The results of applying DBSCAN to the eligible map-matching gaps.

Description	Count	%
Eligible map-matching gaps	29,151	—
Gaps ignored during DBSCAN	14,121	48.4
Anomalies identified	157	—

Analysing the distribution of the number of gaps per anomaly, we could verify that of the 157 anomalies obtained, 125 anomalies had fewer than 100 gaps. On the opposite side, nine anomalies contained more than 420 gaps. In particular, the two most significant anomalies contained more than 1000 gaps. Although anomalies are recorded in various areas of the city, this relative distribution shows that certain areas require greater prioritisation. Targeted interventions in these high-density clusters can benefit a substantially larger number of users.

Anomaly segmentation

DBSCAN clusters were formed solely based on the geographical location of the midpoints of gap traces. Consequently, an anomaly may include gap traces with similar locations but differing movement patterns (e.g. direction, origin, destination, and distance). In some cases, these differing patterns jeopardise the interpretation process. To simplify anomaly analysis, we could visualise each gap trace individually. However, searching for similar or different patterns within an anomaly containing thousands of gaps with varied movement patterns is time-consuming.

To calculate these trace patterns, we implemented an additional step using the DTW measure to subdivide the gap traces of a cluster into smaller groups matching the same movement pattern. This step is described in Algorithm 1. This algorithm takes as input a set of gap traces that constitute an anomaly and groups them into one or more patterns. It has three parameters: the minimum number of gap traces that have a match (M), the maximum DTW value to consider two gap traces ‘similar’ (T), and the number of ‘similar’ gap traces to consider when computing DTW (N).

In this study, we tested different values and combinations for each parameter, namely, M: [3, 5], T: [15, 25, 30], and N: [10, 12]. It is important to note that our aim was not to optimise and evaluate the performance of this algorithm, but to facilitate the cluster analysis.

Results: Figure 5 shows the number of trace patterns obtained per anomaly. The image shows that the majority of the anomalies (64%) have 1 or 2 trace patterns.

OPEN IN VIEWER

Figure 5.

Cluster segmentation results: The number of trace patterns per cluster.

By visually inspecting the results, we could observe that frequently the two trace patterns with the most gaps represent the same path but in opposite directions, such as the two trace patterns depicted in Figure 6(c1) and (c2). The remaining trace patterns may represent small variations in the path, such as a different origin as depicted in Figure 6(c3), or a completely different path, such as in Figure 6(c4).

OPEN IN VIEWER

Figure 6.

Different levels of analysis: (a) Global, (b) anomaly, (c) pattern, and (d) gap.

Anomaly analysis

To assess the result of our technique, we analysed the results produced in the previous steps. For this purpose, we randomly selected 50 anomalies and visually inspected them to assess their cause of failure. Table 5 shows the results of this assessment process.

OPEN IN VIEWER

Table 5.

Evaluation of the anomalies.

	Count	%
Total anomalies	157	100
Anomalies inspected	50	32
True anomalies	42	84
GPS errors	7	14
Internal errors	1	2

In total, we identified 42 true anomalies, cases where the map-matching algorithm failed to produce the correct representation of cyclists’ traces due to limitations in the road network model. This corresponds to a 84% precision rate. This was especially common when cyclists used sidewalks to avoid travelling along or against traffic, changed roads at unconventional locations, or rode through parks and open spaces.

Another significant source of anomalies was the behaviour of the Mapbox map-matching algorithm, which, when configured for a cycling profile, excludes roads tagged as ‘trunk;’ from the set of eligible paths for cycling. In such cases, the algorithm either failed to return any match or inaccurately snapped the route to the nearest eligible road segment.

We identified 7 cases where map-matching failed due to strong GPS interferences. Some of them were caused by situations where the cyclist remained stationary at a location. The data-cleaning process did not account for these cases, but they could be mitigated by applying specific pre-processing techniques.

We also identified one case where the anomaly was due to the map-matching algorithm. Specifically, this case was caused by two parallel roads. When there are two or more parallel roads nearby, even small interferences in the GPS signal can induce the map-matching algorithm into errors. These types of errors are difficult to identify just by comparing the geometry of both polylines. Even when visually inspecting the results, without the ground truth about the cyclists’ paths, we cannot assert whether they shared the road with motorised traffic or used the sidewalk.

Macro analysis

In a macro analysis, the stakeholders may wish to obtain an overview of the severity of anomalies, monitor how the volume and characteristics of anomalies vary during the day, across city areas or in different cities, and benchmark the overall alignment between cycling activity and the road network model. They may wish to examine how anomalies relate to road accidents, road types, motorised traffic intensity, district characteristics (e.g. residential or commercial) or critical locations (e.g. schools or hospitals). This broad perspective enables cities to identify priority areas and benchmark the design of their cycling infrastructure.

To conduct macro-level analysis, it is ideal to establish a set of metrics that can be computed automatically on a large scale. This approach ensures that the methodology is replicable across different cities, allowing effective benchmarking and comparison. Some of these metrics may be computed at the city level or at a finer spatial scale. The latter describes a neighbourhood or district in finer detail. Additionally, it should be possible to aggregate them into a global metric to represent the overall conditions of the city. Examples of metrics may include the average number of gaps per cycling trip, the average number of gaps per km travelled, the average number of anomalies per neighbourhood, or the average detour ratio per anomaly, in other words: ‘For each anomaly, how much longer is the shortest path that only includes legal routes compared to the path followed by cyclists?’ These metrics help identify how frequently cyclists search for informal travelling paths, evaluate the impacts of current cycling conditions, and quantify the potential for improvement.

Micro-analysis

In a micro-analysis, the focus shifts to identifying the root causes of specific anomalies to plan effective solutions. To achieve a systematic resolution of the main causes, stakeholders may need to combine quantitative and qualitative methods. In other words, they must integrate metrics and visualisations to provide comprehensive insights.

The metrics will enable the establishment of a ranking of anomalies based on their impact on cyclists and potential improvement. This could help stakeholders obtain systematic and actionable feedback, allowing them to prioritise efforts effectively. These metrics may quantify factors such as the number of gaps within an anomaly, the frequency of gap occurrences (in other words, the number of GPS traces registered in one location vs the number of gaps identified), or the impact of anomalies on cyclists in terms of safety, detour, and comfort. This latter metric could enable comparisons between the anomalous path and alternative routes that include only legal paths. To enrich the analysis, it would also be useful to describe the attractiveness of those alternative routes using OSM tags or complementary data sources, such as altimetry data, which can provide information about road gradients. The visualisations provide a qualitative perspective, allowing for comparison of anomalies with the road network and local knowledge.

Workflow analysis

During our work, we explored four visualisation approaches to perform the analysis. Figure 6 illustrates the workflow used for analysing a hotspot and identifying its root cause. This workflow has four steps, namely, the global, anomaly, pattern, and gap views.

Step 1: Global View: We usually start by visualising the locations and the volume of anomalies on the map. Figure 6(a) shows an example where each circle represents an anomaly. The colour and size indicate the number of gaps in each anomaly. This map highlights the spatial distribution of anomalies, allowing stakeholders to identify critical areas in need of intervention.

By applying this workflow, we were able to identify the root cause of several anomalies. In the example provided by Figure 6, we identified several errors in the OSM road network, namely, OSM had no representation for the walkway along the main road, and some connections between residential streets and pedestrian facilities were also missing. These omission errors caused the map-matching algorithm to create detours to connect the map-matched segments and could negatively impact the quality of route suggestions, especially for pedestrians. The probable root cause of this error was the cyclist’s attempt to avoid sharing the road with cars at high speeds, which forced the cyclist to use a pedestrian facility, which is an illegal behaviour.

Based on our experience analysing anomalies, these insights can be valuable to various stakeholders: First, they can help OSM collaborators improve OSM road network data by highlighting missing roads or incomplete tags in the OSM database. Second, they can help urban planners detect zones needing improvement, namely, where cycling has less support and where cyclists engage in illegal behaviour. Finally, these anomalies can help cyclists move more easily across the city by providing new paths, which other cyclists use to avoid unfavourable situations.

Limitations

A limitation in our concept of a map-matching anomaly is the case of parallel roads. This is a very common source of map-matching errors and is particularly common with cycling traces because many cycling routes are created alongside major roads. Since the two roads are very close to each other and essentially follow the same direction, even minor GPS errors can easily lead to map-matching gaps.

Our anomaly concept is not very helpful in these specific cases. There are two possible scenarios, and neither produces a valuable outcome. In the first scenario, both roads are properly described in OSM and are both viable alternatives for map-matching. In these cases, map-matching errors are likely to occur, but they are due to GPS interferences and not a consequence of any limitations of the OSM representation. Therefore, these errors do not fit our definition of anomaly and should not be considered.

The second scenario is when only one of the roads is represented in OSM, but they are both used by cyclists. In this case, all map-matching requests will tend to match to the single road represented in OSM, regardless of which one was actually followed. This should be signalled as an anomaly, as it fits our definition. However, in general, it can be extremely hard to identify these cases as anomalies because there is a route represented in OSM that is not sufficiently distinct from the followed routes. They are so close that, even if they were both represented in OSM, we know that many times the wrong one would be selected by the map-matching algorithm. As a consequence, our anomaly detection algorithm will not be able to define suitable detection thresholds that can distinguish common map-matching errors from a systematic problem caused by the lack of representation in the road network data model. In its current version, which is optimised for all the other types of map-matching errors, it would produce many false negatives corresponding to those cases where the anomaly detection algorithm would not reach the specified threshold because of the proximity between both roads.

Reducing the occurrence of parallel roads would require substantially more accurate GPS devices, which would enable the use of a lower threshold in the anomaly extraction phase. Nevertheless, deploying such high-precision hardware is impractical when collecting large-scale crowdsourced GPS data.

A second limitation of this study is that we only considered the OSM road network to apply our anomaly identification process. Nevertheless, our definition of anomalies is conceptually independent of any specific road network model and is not strongly coupled with OSM. Furthermore, we only considered one map-matching algorithm. The proposed method, however, is expected to be generalisable to other road network models and map-matching algorithms, as its core components require only a set of GPS traces and their corresponding map-matched polylines. Future work could explore how performance varies across different map-matching algorithms, parameter configurations, and road network data models.

Future work

As future work, we plan to improve the performance of our method by exploring additional data-cleaning techniques, such as filtering GPS signals, to mitigate the impact of false positive gaps.

Secondly, we intend to interview key stakeholders in cycling mobility, including cyclists, urban planners, and OSM contributors, to understand their perceptions of map-matching anomalies. If different perspectives emerge, we will explore strategies to reconcile them and assess whether and how OSM can facilitate this reconciliation.

It would also be valuable to explore the perspectives of OSM contributors on using anomalies to automatically update OSM data. Currently, most mapping processes are still predominantly manual. A common approach involves visually comparing the OSM road network with GPS traces to identify and draw new features. This is a time-consuming method, especially for detecting minor omission errors.

Finally, we aim to develop a tool to support the identification of anomalies based on data shared collaboratively. By allowing the community to explore their data, this tool will assist both OSM contributors and urban planners in their daily activities. The first will be able to discover missing information and improve OSM’s database. The latter will be able to identify areas that require intervention.