UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A principled approach to automated road network conflation Agarwal, Gorisha

Abstract

Geospatial databases are gaining tremendous popularity, driven by the need to have digital maps to support various individual and industrial use cases like navigation, logistics, fleet management, ride-sharing, and food delivery. Clearly, maps need to be accurate and up-to-date. While most geospatial databases are proprietary, OpenStreetMap (OSM) is a collaborative good quality crowd-sourced database. The quality of OSM is comparable with many private datasets: OSM is currently being used by many companies worldwide, including Facebook, Apple, Amazon and Microsoft. The contributors volunteer to "draw" the missing spatial features on OSM. Despite continuous meticulous work for more than 15 years now, OSM data still lacks good coverage in many parts of the world. Extending its coverage is a laborious and time-consuming task. There is a pressing need for an automated approach to conflate the missing features from other spatial databases and satellite images. We address road network conflation between two vector geospatial databases and propose MAYUR, solving the major subtasks -- map matching and map merging. We represent geospatial databases as a graph of road intersections (vertices) and lines (edges) with spatial attributes. We propose a novel map matching framework by adapting the Rank Join in databases, where each edge of the reference database graph is a relation. Our algorithm finds the target database graph that best matches the reference database, respecting the connectivity of the road network. Classic Rank Join in databases has been tested on very few relations, and it gets quickly inefficient on instances with many relations. We introduce several optimizations that boost the algorithm's efficiency, making it scalable for our problem setting featuring hundreds to thousands of relations. We establish the node mappings between the two databases using the mapping obtained from the matching step. Our map merging uses rubbersheeting to merge the missing features. We demonstrate the performance of our map conflation approach on sidewalks in OSM and Boston Open Data. Manual evaluation shows that our map matching achieves an impressive 98.65% precision and 99.55% recall, with our map merging causing very small perturbation in the merged features, outperforming Hootenanny, the leading map conflation approach.

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International