Towards highly accurate map services.

Abstract

Map services such as routing, travel time estimation, and nearby facility search have become integral to a broad range of transportation applications including ride-sharing, food delivery, last-mile logistics, and emergency response. Consequently, significant research efforts have focused on developing algorithms for map service queries, commonly under the implicit assumption that the underlying road network is accurate. As a result, these efforts primarily focus on algorithmic efficiency (i.e., execution time). Unfortunately, this assumption is not true, as road network data suffer from various inaccuracies such as missing roads, incorrect edge weights, and inaccurate traffic information, all of which severely degrade the accuracy of query results. No matter how efficient a shortest path algorithm is, or how accurate the map topology may be, the end result will be only as accurate as the edge weights it relies on. Thus, the primary bottleneck in map services today is no longer the efficiency, but rather the accuracy, which heavily depends on the quality of the underlying road network used for these services. The goal of this dissertation is to significantly boost the accuracy of map services and shift the research focus from merely developing more efficient algorithms to improving the accuracy of the underlying map itself. We consider a broader definition of a map that goes beyond traditional topology to a richer one that includes traffic related metadata, without which, most map services would suffer from low accuracy. To this end, we introduce a set of innovative techniques geared towards building the most comprehensive and accurate maps. This dissertation does not aim to develop new algorithms for map services or modify existing ones. Instead, it aims to improve the accuracy of the map itself to provide more accurate input to query systems. This significantly boosts the accuracy of all existing (and future) algorithms without changing their internal logic. This thesis makes the following contributions: First, we introduce RASED, an open-access map analysis tool that we developed to help researchers monitor map updates across the world and gain deeper insights into map quality. Second, we present QARTA, a full-fledged machine learning-based system for accurate map services. It leverages machine learning to (i) learn accurate edge weights for the map from sparse trip data, and (ii) learn and model the map error margins, which are then used to calibrate query answers based on contextual information, including transportation modality, location, and time of day/week. Third, we introduce our vision, “Let’s Speak Trajectories”, which enables the execution of most (if not all) trajectory analysis tasks essential for constructing accurate maps via one unified framework. We draw a novel analogy between trajectories and natural language statements and innovatively adapt the BERT language model to perform these tasks within a single, model-based framework. Lastly, we present KAMEL, a novel system for the trajectory imputation task inspired by our vision. It accurately infers missing points along sparse trajectories, generating dense, high-quality trajectories that enable more reliable map inference for any algorithm using this data as input. In summary, the research contributions in this thesis lay the foundation and provide the means for building comprehensive, high-quality maps that elevate the accuracy of all map-based applications.