Revisiting Graph Sampling for map comparison

Title: Revisiting Graph Sampling for map comparison Author: Jordi Aguilar Larruy Advisor: Rodrigo Ignacio Silveira Department: Department of Mathematics Month and year: June, 2021 Degree in Data Science and Engineering Facultat d’Informàtica de Barcelona Facultat de Matemàtiques i Estadística Escola Tècnica Superior d'Enginyeria de Telecomunicació de Barcelona Universitat Polit`ecnica de Catalunya Facultat d’Inform`atica de Barcelona Escola T`ecnica Superior d’Enginyeria de Telecomunicaci´o de Barcelona Facultat de Matem`atiques i Estad´ıstica Degree in Data Science and Engineering Bachelor’s Degree Thesis Revisiting Graph Sampling for map comparison Jordi Aguilar Larruy Supervised by Rodrigo Ignacio Silveira Department of Mathematics June, 2021 I would like to express my appreciation to my supervisor Rodrigo Silveira for his guidance and bringing me the opportunity to work closely with him and his fellow researchers in an international research project. Thanks also to Kevin Buchin, Maike Buchin, Erfan Hosseini and Carola Wenk for their help during the development of the project. Abstract This project offers a review of the Graph Sampling Method, a metric that computes the similarity between two road networks, commonly used in the context of map construction algorithms. The intuition of this metric is simple: first we sample points from both maps to then match pairs of points, one from each map. A high number of matched points indicates that the maps have a high degree of similarity. Although this metric has gained popularity in the publications related to map construction, we typically find differences in the approaches and the parameters chosen for the metric, causing that the scores of these publications may not be comparable. Often, the details of the implementation are not provided, which causes that the results will be hardly reproducible. The goal of the project is to understand the different implementations that can be found in the two steps of this metric, sampling and matching. Moreover, we study the implications of each choice and compare the advantages and disadvantages of each. We also provide a repository with the implementation of the Graph Sampling Method in order to provide a common metric for the map construction community. Keywords Map comparison, map construction, map evaluation, graph sampling 1 Contents 1 Introduction 3 1.1 Motivation ........................................... 3 1.2 Preliminaries .......................................... 3 1.3 Comparing two maps: previous work ............................. 4 1.4 Context of this project .................................... 5 2 Goals of the project 5 3 Graph Sampling Method 6 3.1 Graph Sampling Distance by Biagioni and Erikson ...................... 6 3.1.1 Compute seeds .................................... 7 3.1.2 Sampling the graph: .................................. 7 3.1.3 Matching: ....................................... 8 3.2 Debugging the code ...................................... 9 3.3 Other implementations .................................... 10 4 How to compare two maps 12 5 Experiments 13 5.1 Sampling experiments: .................................... 14 5.1.1 Connectivity ...................................... 14 5.1.2 Consistency ...................................... 15 5.2 Matching experiments: .................................... 16 5.2.1 Quantitative experiments ............................... 16 5.2.2 Qualitative ....................................... 18 6 Results 18 6.1 Sampling experiments: .................................... 18 6.1.1 Connectivity ...................................... 18 6.1.2 Consistency ...................................... 21 6.2 Matching experiments: .................................... 22 6.2.1 Quantitative ...................................... 22 6.2.2 Qualitative ....................................... 24 7 Conclusions 25 2 1. Introduction 1.1 Motivation Accurate road maps are crucial for travel efficiency and safety. Furthermore, with the arrival of autonomous vehicles (AV), having precise and updated maps is a requirement needed in order to provide an adequate service. During the last years, the creation and the maintenance of road maps has had the support of either high cost surveys or the online community in platforms such as OpenStreetMap (OSM), but this volunteerdriven process suffers from significant variability in both the skill level and availability of volunteers in different parts of the world. It is for this reason, and due to the increase of available data from all kind of sources, that new methodologies to create maps automatically and at a cheaper cost have emerged. Two of the most common approaches to create maps are using aerial imagery and using GPS trajectories. This kind of data can be used to generate entirely new sections of the road network, or to improve the accuracy and detect the changes of existing road maps. To achieve these tasks, one of the primary steps is the comparison and evaluation between two maps since it will allow us to track the performance of our constructing algorithms or to find the differences between two maps. This work will focus on the analysis of an evaluation metric for road maps: the Graph Sampling Method. 1.2 Preliminaries In this section we will illustrate different notions related to the map construction topic to help the reader be more familiar with the different concepts that will be shown during this thesis. Figure 1shows a good example of one of the main tasks that we have faced a lot of times during the course of this research: looking at the output of the Graph Sampling Method. Road map: In this thesis we will mention a lot of times road map,road network or just map. They all refer to a geometric graph, a special case of graphs that are embedded in the Euclidean plane. Each node of this graph has two coordinates, and the edges are straight lines between two nodes. They are not necessary planar (i.e. edges don’t intersect) since it can have features such as bridges. Moreover, they can include more features such as directed edges or turn restrictions. Ground truth and reconstructed map: The ground truth map is the real geometric graph, provided by observation and measurement. The reconstructed map is the inferred map from GPS trajectories. Note that we will refer to the ground truth map as Gand to the reconstructed map as H. In mapconstruction.org examples can be found of both trajectories and ground truth datasets as well as the output of map construction algorithms. Map construction algorithms: These are the algorithms used to build the reconstructed road maps. In this work we will be working with maps outputted mainly from algorithms that transform GPS trajectories into graphs. This algorithms belong to the area of computational geometry. Graph Sampling Method: The main topic of this thesis: the Graph Sampling Method. The utility of this method is to compare one road map to another one. It consists of two steps: the first one samples 3 Graph Sampling Method Figure 1: Two road maps (red, blue) and graph sampling results: matched points are connected by pink lines, unmatched points are yellow or orange. points from each map, the second one matches pairs of points from both maps in a 1-to-1 fashion. The more points matched, the more similar the maps are considered. 1.3 Comparing two maps: previous work The need of evaluating quantitatively a reconstructed map was acknowledged already in 2012 by Liu et al.. In [17], they explain the issue of having only qualitative evaluations that rely on “eyeball” tests and enumerate some reasons to have a quantitative metric. The reasons were the following: 1. Measurement of progress in the field 2. Comparison of many algorithms in one plot 3. Use of machine learning techniques to derive parameter choices from training data In this same paper, a metric that computes the precision and the recall of a map is presented. It follows a similar pattern than the graph sampling technique: taking samples only in the ground truth, we compute which portion of this samples are within a perpendicular distance threshold mto a (nearest) edge in the reconstructed map. Since we take samples every meter, the total number of samples can be though as the total distance correctly predicted. Finally, to obtain the recall we divide the correctly predicted length by the length of the ground truth. To obtain the precision, the correctly predicted length is divided by the length of the reconstructed map. This same year, Biagioni et al. introduced in [7] the foundations of what will be one of the most popular methods for evaluating a reconstructed road map. He distinguished two different approaches, the global one (which is called GEO) and the local one (which is called TOPO). The idea of GEO is to take samples on both maps to then try to perform a 1-to-1 matching between both sets. In order for two points two be matched, they must fulfill some criteria like a maximum distance between them or a maximum difference in the orientation of their edges. TOPO adopts the same idea but it is implemented in a more sophisticated way: first we generate random points (also called seeds) in the ground truth. Then, for each of this seeds we traverse the edges of the map starting at the seed and taking samples only if we are within a radius from the seed. For the reconstructed map, we do the same procedure starting at the edges close to the seed. Once we have samples in both maps, we proceed to match them following a certain rule and we move to the next seed. The key idea is that for each of these seeds we are only traversing those edges connected with the initial edge(s). This means that if the map has issues with the connectivity (it either has too many connected edges or too many disconnections between edges) we are going to take them into account. The local approach is described in detail in section 3.1. 4 scenarios will not have a big impact in the number of samples if the sampling interval is small and the edges of the maps are sufficiently large. The sampling process of the local sampling approach has however more caveats that can cause significant differences between implementations. We can find the first issues deciding the number of seeds that are going to be used. Some papers do not provide this number, and other papers like [14,15] state that they place seeds with a separation of 50 meters. In the first case it is common to place the seeds randomly, making the reproducibility of the evaluation unfeasible. A second source of variability related to seeds is how to choose the initial edge to begin with the graph traverse. As explained in Section 3.1.2, Biagioni’s implementation chooses all edges within edge distance threshold, which happens to be the same as match distance threshold. An alternative can be to choose only the closest edge and not all the available ones. This may be the difference between sampling a single connected component or more than one. When using the local sampling approach one can also decide whether to respect the turn restrictions and the one-way streets, aside from including extra conditions such as that the traversing must lead away from the seed. Lastly, deciding which sampling distance threshold is going to be used can have a big impact on the connectivity that we are capturing. In the literature we can find values that include 100m[10], 300m [12,14,3,2,9,8,7] and even 2000m[19]. Matching the samples: Once we have two sets of samples (one of each map), we want to match pairs of points from both sets. A matching between a pair of points implies that the point in the ground truth has found a valid point in the reconstructed match which can be considered the same. A match also implies a correct prediction, so it is important to find a matching rule that aims at matching points that could be the same and has the right balance between being too selective or too inclusive. In this section we are going to define three different rules: Maximum Matching (MM), Greedy Matching (Greedy) and Weighted Maximum Matching (WMM). The third one is a new matching rule proposed in our submitted paper. The first one has been used by [14] and the second one was found in the code by Biagioni and Erikson [7]. We are not aware of any other kind of implementation, in fact, most papers do not explicitly describe how the matching is done, they explain that it is a 1-to-1 matching and that two points are matched whenever they are within match distance threshold. Maximum Matching (MM): In this matching, for each sample in the ground truth set we define a set of candidates in the reconstructed map that fulfill the distance condition. Then, following a 1-to-1 match the matching algorithm maximizes the total number of matches. It is interesting to notice that no distinction is made between the samples that are within the set of candidates. Greedy Matching (Greedy): Computing a maximum matching can be costly and generate solutions where the points matched seem to not correspond to the same point in both maps (see Figure 8). It is for this reason that one can come up with a greedy matching that offers a fast but suboptimal solution. Since the distance between two points is the main factor when it comes to decide whether there should be a match, one could think of a greedy matching that prioritizes the closest available match. In the case of Biagioni and Erikson [8], they implement a matching where the shortest available pair of points is matched provided that they fulfill three requirements: the distance between both points is within match distance threshold, the inclination between the edges is less than bearing difference threshold and the point in His among the neighbourhood threshold–nearest neighbours of the sample in G. This algorithm is thoroughly explained in Section 3.1.3 and described in Algorithm 1. Weighted Maximum Matching (WMM): Finally we propose a matching that maximizes a function that takes into account the length of the matchings. For a sample in the ground truth, we consider the same candidates as in the Maximum Matching, but this time we add a weight to each pair defined as 11 Graph Sampling Method match distance threshold − ||p−q||, where ||p−q|| is the Euclidean distance between p and q. The idea now is that the algorithm has to maximize the total weight of the matches, enforcing short matches. This option can produce as many matches as MM, but we know that they are going to take into account the length between matches. The main difference with the Greedy is that we get rid of the parameter of the neighbours and that in the Greedy algorithm a point will have a unique pair, whereas in WMM, a point may change its pair according to match distance threshold. Computing the scores: Precision and recall are the two scores typically used to quantify the results of the graph sampling method. In this context, precision is measured as the number of matched samples divided by the total number of samples on Hand recall is the number of matched samples divided by the total number of samples on G. This two scores are usually merged using the F-score, defined as F= 2 ·(precision ·recall)/(precision +recall). In global sampling, measuring the precision and recall is straight-forward since we sample a single time the whole map and do a single matching. Hence, we can clearly define the set of matched samples, the set of samples on Hand the set of samples on G. However, when using local sampling we have multiple iterations of the ”sampling-matching” process. Moreover, there are seeds where we can’t find any edge of Hclose to that seed. In this case two approaches can be taken: the first one is to ignore those seeds that do not have sampled points in Hor the other case is to consider them only for the recall. To compute the results of local sampling we have found two different options in the literature. The first one is to compute the precision and recall aggregating all samples over all seeds as described in Section 3.1.3 and the other option is to take the mean of the precision and recall of each seed. One last detail about the evaluation of two maps that affects equally the global sampling and the local sampling is cropping the ground truth. It is common to find ground truth maps that contain multiple roads that have not been covered by any trajectory or with an area much larger than the one covered by trajectories. In this cases, recall may be substantially lower since it will be very hard for the reconstruction algorithm to find those roads. It is for this reason that in some works the ground truth is cropped in a way that only contains the roads traversed by trajectories. Doing this is not trivial and adds an extra source of variability. Some ways to do this is manually [20] or using map-matching algorithms like in [8]. 4. How to compare two maps In Section 2were we define the goals we state that we need to define some requirements that should be the basis to argue whether the evaluation algorithms do a proper job or not. These requirements will help us to verify to what extent the evaluation metrics meet them. Otherwise, it is going to be really hard to compare the different methods to evaluate maps. When comparing two maps, two main factors have to be evaluated: the geometry and the topology. Geometry takes into account if a map is overlaid over the second one, that is, if a road (or a segment of a road) is represented in both maps. Topology cares about the connections of the graph, the degree of the intersections, the cycles of the graph or the paths between two points of the graph. However, before diving into how does the evaluation metric have to deal with this topics we will focus on what is the degree of importance that the evaluation metric has to put into each part of the map. Road maps are composed of streets, highways, avenues, streets where each direction has a different edge... One may think that from a practical point of view, streets that are crowded must be more relevant when comparing two maps, or that attention must be paid to areas with a high density of roads. On the other hand, we could make no 12 assumptions about each road of the map and just evaluate them in function of their length. Other criteria may be that each edge has to have the same importance regardless of their length, or that each edge has to have a weight proportional to the time it takes for a vehicle to cross it: this way, a very long highway would have the same importance as a handful of short and complex streets of a city center, since, at the end, it takes the same time to complete these two trajectories. In this work, we will make no assumptions about the features of the edges, and we are going to consider that the length is the only thing that matters: one edge that is half the length of another should have half the weight in the final score. Going back to geometry and topology, how can an evaluation metric take these factors into account? To evaluate the geometry of the map one could think that given a point sGin the map G, we should identify the point sHin Hthat exactly corresponds to sG(if it exists) and match them. The main problem is that finding sHis not trivial since the perturbation and noise of GPS traces plus the imperfections of the reconstruction algorithms produces that sHmay not be the closest point of Hto sG. However, one should set a limit to the search area since ultimately each node of a road network has its fixed coordinates in the space, and despite the noise of the GPS traces we should enforce a matching between points that are close in the space. A second key aspect is that hopefully we do not only want to match pairs of points, but we want to consider the map as continuous as possible. This means that ideally we would be able to match sub-edges of both maps or even sets of edges that encompass large regions of the road network. Intuitively, we are willing to find the minimum edit distance between both graphs in a continuous fashion. However, putting this idea into practice is not easy, since taking into account the position of the nodes of the graph is a crucial step in this task. Furthermore, we have to think on how to translate this idea of merging one map into another in a single score that will be used to compare different algorithms and do it in an efficient and feasible way that is not computationally expensive. The final idea is that an evaluation metric should be deterministic and easy to reproduce, otherwise, it will loose a lot of value given that researchers won’t be able to use the scores published in the papers to compare with their own experiments. The following experiments will help us to determine whether the different approaches of the graph sampling method behave according to the conditions stated in this section. 5. Experiments The aim of this section is not only to describe which experiments are going to be carried out and how are we going to do them, but to give a meaning to each one of them, to understand why are we doing these experiments. During the course of the thesis, I have personally faced a situation that was new to me, doing ametaevaluation: ”a systematic and thorough evaluation of an assessment methodology” [18]. Realizing this raised two main concerns. The first one was how to assess the performance of an evaluation metric. To do it, first we need to know which aspects do we think that the evaluation metric has to take into account or what is the expected behaviour of the evaluation metric in different scenarios. The second main concern was how to do it. In the world of research it is common to find several metrics that evaluate the performance of a model in a given task, the success or failure of a methodology or whether a hypothesis has been confirmed or rejected. Even for the task of comparing a reconstructed map to a ground truth it is possible to find many types of metrics that range from simple and straight-forward counting of nodes and edges and doing ratios to hours of computation to find the edit distance of two graphs. However, finding the right way to evaluate an evaluation metric is not so extended in the literature and not trivial to find. We need to know what are we asking to the metric. For example one should know if the metric should 13 Graph Sampling Method fulfill a general property, have a specific behaviour in a predefined test case or meet some constraints in its output. It is for this reason that we are going to use Section 4to as the main requirements that we think that a comparison metric between two maps has to take into consideration. With this requirements, and with the help of the experiments, we will be able to ultimately find limitations, categorize and distinguish the different approaches related to the graph sampling metric that are used to compare two maps. 5.1 Sampling experiments: The first set of experiments will be the ones concerning the different ways to sample the graph. With them, we want to understand the implications of choosing local sampling or global sampling. 5.1.1 Connectivity One of the major claims of the TOPO method is that, as the name indicates, it takes into account the geometry of the graph as well as the topology. This term is a bit general and one may wonder what exactly the topology of a graph is. Instead, we prefer to say that the TOPO method measures the geometry of the graph and its connectivity. Given that for a specific seed, samples are dropped starting at edges closer than edge distance threshold until a maximum radius of sampling distance threshold, it exists the possibility that one edge within that radius that is not part of the connected components of the selected edges will not be sampled. If, for whatever reason, our reconstructed map Hdoes include this edge among one of the initial connected components, we will end up with extra samples in this edge that are not present in G. Having more samples in Hthan in Gwill potentially cause a decrease in the precision since we won’t be able to match those samples that are not present on G. The same example can be applied exchanging the maps: if Hhas disconnected edges that are connected in G, the recall will be lower since we are not sampling edges that will be sampled on G. This will be useful to punish those algorithms that tend to connect to many edges that shouldn’t, or to disconnect edges that should be connected. This is also helpful to take into account features of the map such as bridges, tunnels, intersections of several edges, urban highways... In Figure 2we can observe the behaviour of the local sampling. Two almost identical maps (blue and red) are shown, the blue map is a single connected component, while the red map has two separate connected components. The cross (”x”) in the figure shows the placement of the seed. We can see that we are only sampling one connected component of the map in red, the closest to the seed, whereas in the blue map we put samples everywhere. While there is no doubt that to do a complete evaluation of a map at some point you have to take into account the connectivity, we ask ourselves whether this option of merging it with the geometry of the graph is adequate. In particular, we are going to (1) manually build a small test to verify the eventual decrease of the scores when there are issues with the connectivity of the reconstructed map. We want to compare what happens when we evaluate one example with poor connectivity using local sampling versus using global sampling. Another possible concern about the local sampling is the location of the initial seeds. One can think that seeds are uniformly placed along the length of the graph, but this is not true if seen from a perspective of the area that they reach. Take for example the disk created by a seed in an area with high density of edges: there are high chances that within that disk we will find more seeds. The disks formed by these seeds will overlap, hence, the edges that are in high density areas will be sampled more times. On the other hand, edges that are placed in very sparse areas will have less seeds close to each other, thus, there 14 Figure 2: Two manually created maps (blue and red). The cross (”x”) in shows the placement of the seed. Orange points are samples in the blue map, yellow points are samples in the red map. will be less overlapping of disks. We are going to (2) analyze this situation through a predefined example where we emphasize high density areas and low density areas and compare the behaviour of local sampling versus global sampling. 5.1.2 Consistency Another claim stated in [8] is that global sampling is a robust method to compare two maps. However, we know that it adds two extra parameters (num evaluations and sampling distance threshold) that are not needed in the local implementation. Moreover, the use of seeds introduces two more decisions that may cause variability to the final score: the choice of what to do with seeds that are not close enough to and edge of Hand the way to compute the scores once the matching has been done. It is for this reason that we want to analyze the variance of the final score when we change the value of some parameters. Hopefully we would like to find that the f-score doesn’t have too much variability when using different values for the parameters. Otherwise, one could fine-tune the parameters of their evaluation metric to achieve the higher available score. This could lead to two situations that are unfavourable to distinguish which are the best models: the first one is that a specific configuration of parameters may cause a significant change in accuracy of the models and eventually change the order of best algorithms. The second one is that if you were to compare your own new model against the previous algorithms in the literature, you could not rely on the scores provided in the previous publications unless they use the very same configuration of parameters that you plan to use (remember that for example in Biagioni’s local implementation there are up to 6 different parameters, and several implementation details that are not trivial). This means that you have to obtain the corresponding outputs of the models or even the models themselves to generate the necessary outputs that you plan to compare. It is true that in some publications it is possible to find figures that illustrate the score of the algorithms with various values of a given parameter, but the most common choice is to only change the match distance threshold. The first two experiments will compare the robustness of local against global when changing two param15 Graph Sampling Method eters that they have in common that are the (1) match distance threshold and the (2) sampling interval. Then we will compute the variance that the local approach has when changing their own parameter that is the (3) sampling distance threshold. 5.2 Matching experiments: The second set of experiments will be performed to assess the behaviour of the different matching criteria. We will evaluate three different approaches. The first one will be the maximum matching that maximizes the total number of matched pairs, the second one will be the weighted maximum matching that generates matches such that the total sum of the weight of each match is maximum. In our case, the weight of each possible match will be match distance threshold − ||sG−sH||, where ||sG−sH|| is the distance between the pair of points, one from each map. Intuitively, this prioritizes shorter matches. The third algorithm will be the Greedy matchings, described in Section 1. 5.2.1 Quantitative experiments As we described in Section 4, the matching process in the graph sampling algorithm should try to relate the areas of the two maps that are meant to be the same, nevertheless, we still need to figure out a way to verify if the respective matchings meet the requirements and properties we are asking for. To achieve this, we have come up with five metrics that are closely related with the properties we are trying to find in the matchings and that will help us to distinguish and rank the different matchings available. To test the matchings, first we will generate the samples using the global sampling approach (with asampling interval of 5m) to keep the experiments simple and avoid possible variations that the local sampling may cause. We will compare the three matchings in two different datasets: in Chicago vs the reconstruction of Roadrunner [14] and in Athens vs the reconstruction of Buchin [9]. The maximum matching distance will be set to 50m. Connected sets: We will define a connected set as a set of consecutive matches. How are we going to define consecutive matches? We will consider that two matches (sG 1,sH 1), (sG 2,sH 2) are consecutive matches if the samples sG 1and sG 2are neighbours in G. The same must happen for the samples in H. Two samples sG 1and sG 2are considered as neighbours if, traversing the graph Gstarting at sG 1,sG 2is among the immediate next samples visited. Notice that almost all the samples will have two neighbours, one at each side, but neighbours that are at the end of an edge can have as many neighbours as the number of edges in the intersection. One further restriction is that the two matches (sG 1,sH 1), (sG 2,sH 2) can’t intersect. That is, the line segments that connect each pair of points must not cross. To solve the problem of counting the number of connected sets in an efficient way, we create a graph where each sample is a node, and nodes are connected if they are neighbours. Then, the problem is reduced to counting the number of connected components of this graph. The number of connected sets gives us a lot of information. As stated in Section 4, we want a matching that relates both maps in a continuous way, ideally we are not just connecting points of two maps, but connecting whole areas of both maps eventually composed of several edges. Measuring the number of connected sets can give us an idea if the matching algorithm tries to look for this correspondences of sections between both maps. We could even look for the size of these connected sets: we could take the mean to not only see how many sets we have but also how big are them, or we could count the proportion of sets with a size bigger than i.e. 5 matches. However, in our experiments we are only going to retrieve 16 the number of connected sets, and we are aiming for a low number of connected sets, since it will be an indicator that the algorithm matches whole sections. We provide an example where the connected sets of a matching between two maps are differentiated using different colors for each set. Figure 3: Two maps, one in blue and the other in red. Connected sets are colored in a different color each. Number of intersections: This metric counts the total number of crosses among all the matches. For two matches (sG 1,sH 1), (sG 2,sH 2), we will say that they intersect if the line segments between (sG 1,sH 1) and (sG 2,sH 2) intersect. Recall that we are talking about segments, not lines. A good matching aims to relate two maps with the smallest possible effort. Given Theorem 5.1, which states that intersections will produce greater distances between the pairs of points, it is logical to think that having few intersections will mean that our matching algorithm is able to connect points in a way that it creates matchings that have minimum length, which can be a good way to justify that our algorithm matches points using the smallest possible effort. Theorem 5.1. Given the points (sG 1,sG 2) belonging to G and the points(sH 1,sH 2) belonging to H, the two 1-to-1 matches from G to H such that the sum of their lengths is the shortest one will not intersect. We will prove it by contradiction and using theorem 5.2 Theorem 5.2. The sum of two sides of a triangle is larger than the third side. (Triangle Inequalty [21]) Proof. Given the points (sG 1,sG 2) and (sH 1,sH 2) and two 1-to-1 matches that intersect between these two sets, these two matches can be thought as the diagonals of the quadrilateral that wraps the four points. Given Theorem 5.2, we know that the sum of both diagonals will be greater than the sum of two opposite sides. Mean length: We have seen that counting the number of intersections is closely related with the length of the matches. Moreover, we believe that a short distance between the two points of a match means a shorter displacement of the maps in order to become the same map. So a good way to evaluate if a matching algorithm focuses on minimizing the displacement between two maps is by computing the mean length of a match. This metric is much more straight-forward than the previous one where we counted the number of intersections. With this metric we will know the average distance between two matched points, 17 Graph Sampling Method which not only gives a look at how well the map that you are evaluating is constructed but also will serve as a comparison metric between matches algorithms to determine which is the most tightened one. Neighbour rank: We are going to define the neighbour rank of two samples (sG,sH) as the minimum ksuch that sHis between the k–nearest neighbour of sG. This metric has a similar purpose than the metric number of intersections and the metric mean length: we want to know if our matching algorithm is prioritizing shorter matches over larger matches. However, as the number of intersections does, we are not explicitly taking into account the distance of the match, we are evaluating the proximity of the matches looking at their degree of neighbourhood. One can assume that if a match has discarded a high quantity of samples that are closer to the actual matched point, chances are that these two points do not belong to the same coordinate of the map, and our matching algorithm has been too tolerant in the matching. In fact, this is probably what Biagioni had in mind when he added the restriction of the 10–nearest neighbour to his matching algorithm. In the section of results (Section 6) we will find if this captured by this metric. Maximum (bottleneck) distance: Finally we will take into account a metric that searches the distance of the longest match that has been done. This metric will give us an upper bound of the matches produced by an algorithm in a particular pair of maps. It will help us to identify if a particular matching algorithm is really ambitious and tries to match at all costs or if on the other hand the algorithm gives a little bit of slack to the match distance threshold and produces matches that are less close to this threshold. 5.2.2 Qualitative The metrics described in the previous section will be really useful to obtain insights about the general properties of the matching algorithms and also to be able to compare numerically each matching. However, we are also interested in understanding the behaviour of these algorithms in a specific context. In particular, we are going to generate two small tests that contain really simple shapes and features that could be found in a map and evaluate them using the different matching algorithms. From that, and based on the arguments described in Section 4, we are going to point out what is the correct behaviour of a matching algorithm in that particular situation and which are the advantages and disadvantages that we can observe in the tests. 6. Results In this section we are going to explain the results obtained in the experiments described in section 5. 6.1 Sampling experiments: 6.1.1 Connectivity The first experiment that we are going to perform is (1) the evaluation of the behaviour of the local sampling in a predefined test. In Figure 4we show the same example as in Figure 2but this time with 50 seeds. Each circle is associated to a seed, and the color indicates the F-score of the seed. In this example we can ignore sampling distance threshold since it is larger than the graph itself. We can see that the seeds in the vertical edge have the lowest score since they are associated with the shortest edge of the red map. On the other hand, seeds in the top edges have a higher score. We can appreciate that seeds right 18 in the middle of the graph have the highest score since we are sampling both connected components of the red map. The precision of this example is almost 1, 0.983 precisely. However, the recall is much lower (0.556) although both maps are really similar and occupy almost the same region of the space. In fact, this recall can be computed by hand: we know that 2/3 of the seeds in the blue map (the ones placed in the two upper edges) will have a recall of 2/3 since we will only cover 2/3 of the red map. In contrast, 1/3 of the seeds will have a recall of 1/3. Hence, Recall =2 3·2 3+1 3·1 3=5 9≈0.555. When evaluating this example using global sampling we obtain a precision of 0.964 and a recall of 0.931. This example already shows that local sampling goes way beyond than the standard definition of recall (ratio of ground truth covered), and it depends on the connectivity of the graph. In particular, we can see that it depends heavily on where the disconnection is. If we have a disconnection in a central node, recall is going to be heavily punished. If the disconnection is in a isolated region we will barely notice it. Of course, it also depends on the sampling distance threshold, since this parameter will define the neighbourhood that we are going to sample. Figure 4: Two manually created maps (blue and red). The crosses (”x”) show the placement of the seeds. Orange points are samples in the blue map, pink points are samples in the red map. The disks illustrate the F-score of each seed, the brighter (yellow) the higher the score. Density issues (2) are evaluated in Figure 5and Table 1. Among the three figures in Figure 5, the only thing that changes is the position of the map 2. In Figure 5a,map 2 is over the grid (the dense zone), in Figure 5b the reconstructed map is over the big cycle (the sparse zone) and in Figure 5c the reconstructed map is distributed among the dense area and the sparse area, in particular it is placed over two of the six squares of the dense area. In the plots, the crosses represent the seeds and each seed has its corresponding disk of radius sampling distance threshold. The color of the disk is associated to the F-score of the particular seed. The brighter (yellow), the higher the value of the Fscore of the seed. Table 1shows the different scores obtained for each example using three different approaches described in Section 3.3. In this example we are not interested in the precision since it is almost 1 in all the cases, instead we are interested in the recall. Looking at the GEO evaluation, we can see that the recall value is always around 0.5. In fact, the examples have been built in a way that the reconstructed map has half the length of the ground truth in all the cases. If we look closely at the scores provided by TOPO, we can see 19 Graph Sampling Method that TOPO (agg.) boosts the recall in Dense 5a and drops it in Sparse 5b. This is because the seeds in the dense areas have roughly two times the samples of the seeds in the sparse areas. Aggregating the seeds causes that those seeds with more samples (in dense areas) will have a higher weight. Note than in Mix 5c, this effect is compensated. On the other hand, TOPO (mean) has a lower although noticeable variance in Sparse 5b and Mix 5c, going from 0.451 to 0.571 in two different examples that have the same length of reconstructed map. While it is true that by taking the mean of each seed we are hiding a bit if a seed has a lot of samples or just a few, the fact that we can’t control the overlapping of the disks adds variability to the final score. It is interesting to note that these examples don’t even have connectivity issues, a thing that shows that the local sampling is a method that has more variance than GEO anyway. (a) Dense (b) Sparse (c) Mix Figure 5: Example illustrating the behaviour of local sampling in three different scenarios. Two maps are compared, map 1 with blue edges and map 2 with red edges. 50 seeds are shown with a ”x”. Each seed has a disk of radius sampling distance threshold associated. The brighter the color (yellow), the more accurate the region of the reconstructed map. A sample matched in map 1 is shown in cyan and a sample in map 2 is shown in pink. Sampling distance has been set to 5m,match distance threshold = 15mand sampling distance threshold = 75m In the examples above we have shown that although TOPO does take into account the connectivity of a map, it introduces a lot of variance that makes the interpretability difficult. On the other hand, with GEO we have a clear knowledge of what precision and recall means. Their meanings, the ratio of correct 20 take into account the connectivity of the map, it does it at the cost of losing interpretability. F. Bastani et al. show these same concerns in [6], saying that “TOPO tends to assign higher scores to noisier maps, and thus don’t correlate well with the usability of an inferred map. Additionally, the metrics make it difficult to reason about the cause of a low or high score”. It must be said that this metric is a really good tool to measure the accuracy of the map in a local scale as shown in Figure 6. On the other hand, the global approach improves the variance introduced in the local approach. Moreover, it uses fewer parameters and avoids a lot small details in its implementation. On a negative note, we have to remember that the global implementation does not take into account the connectivity of the graph. However, summarizing the comparison of two maps in a single number is a bit optimistic and it is a good practice to test a new algorithm in a set of different evaluation metrics. Having this in mind, we think that the global graph sampling approach is a good metric to obtain an initial comparison between two maps. Another important aspect presented in this report is the importance of matchings. Although it is a topic that has been overlooked in a lot of papers, we explain why it is important to choose a matching that is coherent with the requirements of a fair comparison between two maps. We show that the greedy algorithm does a good job although the constraint of the 10–nearest neighbours doesn’t allow to scale the match distance threshold and may yield to generalization problems if we work with different sampling interval (5 meters is the default) or in other contexts rather than maps where the neighbour constraing may be too selective. We present a weighted maximum matching algorithm that is mathematically well defined and exhibits a similar or even better behaviour than the greedy matching at the cost of being computationally expensive. Overall, this report tries to shed some light over the evaluation of a reconstructed map when using the graph sampling technique. As mentioned in the Introduction 1, back in 2012 the lack of a quantitative metric made it hard for the map construction community to compare and rank their algorithms. Nowadays several techniques have emerged, being the graph sampling technique one of the most popular. However, the lack of a unified version complicates the interpretability of the different scores presented in the publications and forces the researchers to do their own evaluations of all the algorithms they want to compare. To this end, along with the other researchers involved in this task we make available an implementation of the global graph sampling technique in Github (https://github.com/Erfanh1995/GraphSamplingToolkit) as well as a Visualizer (see Figure 10) and a map cropper algorithm in order to ease the job of evaluating a map and consolidate a common tool and implementation that hopefully will lead to more fair comparisons between the different publications related to map construction. References [1] M. Ahmed, B.T. Fasy, K.S. Hickmann, and C. Wenk. Path-based distance for street map comparison. ACM Trans. Spatial Algorithms and Systems, page 28 pages, 2015. [2] M. Ahmed, S. Karagiorgou, D. Pfoser, and C. Wenk. A comparison and evaluation of map construction algorithms. Geoinformatica, 19(3):601–632, 2015. [3] M. Ahmed, S. Karagiorgou, D. Pfoser, and C. Wenk. Map Construction Algorithms. Springer International Publishing, first edition, 2015. [4] H.A. Akitaya, M. Buchin, B. Kilgus, S. Sijben, and C. Wenk. Distance measures for embedded graphs. Computational Geometry: Theory and Applications, page 101743, 2021. 27 Graph Sampling Method Figure 10: The Visualizer software allows to show the result of the Graph Sampling technique. Aside of the ground truth map and the reconstructed map, we can show or hide the matched/unmatched breadcrumbs, the matched pairs and the input trajectories. [5] H. Alt, A. Efrat, G. Rote, and C. Wenk. Matching planar maps. Journal of Algorithms, pages 262–283, 2003. [6] F. Bastani, S. He, S. Abbar, M. Alizadeh, H. Balakrishnan, S. Chawla, S. Madden, and D.J. DeWitt. Roadtracer: Automatic extraction of road networks from aerial images. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, 2018, pages 4720–4728. IEEE Computer Society, 2018. [7] J. Biagioni and J. Eriksson. Inferring road maps from global positioning system traces: Survey and comparative evaluation. Transportation Research Record: Journal of the Transportation Research Board, 2291:61–71, 2012. [8] J. Biagioni and J. Eriksson. Map inference in the face of noise and disparity. In Proc. 20th ACM SIGSPATIAL GIS, pages 79–88, 2012. [9] K. Buchin, M. Buchin, J. Gudmundsson, J. Hendriks, E. Hosseini Sereshgi, V. Sacristan, R.I. Silveira, F. Staals, and C. Wenk. Improved map construction using subtrajectory clustering. In Proc. 4th ACM SIGSPATIAL LocalRec Workshop, pages 5:1–5:4, 2020. [10] C. Chen, C. Lu, Q. Huang, Q. Yang, D. Gunopulos, and L. Guibas. City-scale map creation and updating using gps collections. In Proc./ 22nd ACM SIGKDD, page 1465–1474, 2016. [11] O. Cheong, J. Gudmundsson, H. Kim, D. Schymura, and F. Stehn. Measuring the similarity of geometric graphs. In International Symposium on Experimental Algorithms, pages 101–112. Springer, 2009. 28 [12] A. Van Etten. City-scale road extraction from satellite imagery v2: Road speeds and travel times. In IEEE Winter Conference on Applications of Computer Vision, WACV CO, USA, March 1-5, 2020, pages 1775–1784. IEEE, 2020. [13] P. Fang and C. Wenk. The fr´echet distance for plane graphs. In European Workshop on Computational Geometry, pages 62:1–62:5, 2021. [14] S. He, F. Bastani, S. Abbar, M. Alizadeh, H. Balakrishnan, S. Chawla, and S. Madden. Roadrunner: improving the precision of road network inference from GPS trajectories. In Proc. 26th ACM SIGSPATIAL GIS, pages 3–12, 2018. [15] S. He, F. Bastani, S. Jagwani, M. Alizadeh, H. Balakrishnan, S. Chawla, M. ˜ M. Elshrif, S. Madden, and M.A. Sadeghi. Sat2graph: Road graph extraction through graph-tensor encoding. In Proc. 16th European Conference on Computer Vision, volume 12369 of Lecture Notes in Computer Science, pages 51–67. Springer, 2020. [16] S. Karagiorgou and D. Pfoser. On vehicle tracking data-based road network generation. In Proc. 20th ACM SIGSPATIAL GIS, pages 89–98, 2012. [17] X. Liu, J. Biagioni, J. Eriksson, Y. Wang, G. Forman, and Y. Zhu. Mining large-scale, sparse GPS traces for map inference: comparison of approaches. In Proc. 18th ACM SIGKDD, pages 669–677, 2012. [18] Pam M.S. N. ”metaevaluation,” in psychologydictionary.org, 2013. [19] R. Stanojevic, S. Abbar, S. Thirumuruganathan, S. Chawla, F. Filali, and A. Aleimat. Robust road map inference through network alignment of trajectories. In Proceedings of the 2018 SIAM International Conference on Data Mining, CA, USA, pages 135–143. SIAM, 2018. [20] J. Tang, M. Deng, J. Huang, H. Liu, and X. Chen. An automatic method for detection and update of additive changes in road network with GPS trajectory data. ISPRS Int. J. Geo Inf., 8(9):411, 2019. [21] Eric W. Weisstein. ”triangle inequality.” from mathworld–a wolfram web resource. 29