Algorithms for map construction and comparison

Analyzing and mining various kinds of geo-referenced data is important in many application areas. We use two types of data: geo-referenced trajectories, such as vehicular tracking data, as well as geo-referenced graph data, such as street maps. This dissertation consists of two main parts. In the first part, we consider the problem of constructing street maps from geo-referenced trajectories: Given a set of trajectories in the plane, compute a street-map that represents all trajectories in the set. In this part, we have two main contributions. First, we present a scalable incremental algorithm that is based on partial matching of the trajectories to the graph. For the partial matching we introduce a new variant of partial Fréchet distance. We use minimum-link paths to reduce the complexity of the generated map. We provide quality guarantees and experimental results based on both real and synthetic data. We further present two multi-thresholding techniques for density-based map construction algorithms. Multi-thresholding is necessary because some streets are travelled more heavily than other streets (highways vs. neighborhood streets), which results in different sampling densities, and thus, one threshold fails to capture all the streets. We present a new thresholding technique that uses persistent homology combined with statistical analysis to determine a small set of thresholds that captures all or most of the significant topological features. We also formalize the selection of thresholds in a density-based map construction algorithm for different variants of uniform sampling. In part two of the dissertation, we consider the map comparison problem: Given two street-maps embedded in space, quantify their differences. Given maps of the same city collected from different sources, researchers often need to know how they differ. Map comparison is very important in the field of transportation network analysis as well as to assess the quality of map construction algorithms. We present a new path-based distance measure to compare two planar geometric graphs that are embedded in the same plane. Our distance measure takes structural as well as spatial properties into account. We show that it can be approximated in polynomial time and it preserves structural and spatial properties of the graphs. We provide experimental results comparing vendor quality street maps (TeleAtlas) with open source maps (OpenStreetMap), as well as maps generated by map construction algorithms with ground-truth maps (OpenStreetMap).