Back to search

University of British Columbia

A principled approach to automated road network conflation

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Agarwal, Gorisha
Contributors dc:contributor
  • Lakshmanan, Laks V. S., 1959-

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/78446

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Agarwal, Gorisha. A principled approach to automated road network conflation. master's thesis, University of British Columbia, 2021. http://hdl.handle.net/2429/78446