Kharita; Robust Map Inference using Graph Spanners

Kharita: Robust Map Inference using Graph Spanners


Rade Stanojevic


The widespread availability of GPS information in everyday devices such as cars, smartphones and smart watches makes it possible to collect large amount of geospatial trajectory information. A particularly important, yet technically challenging, application of this data is to identify the underlying road network and keep it updated under various changes. In this talk I will present our efforts in inferring the road network using the GPS traces. Our approach, called Kharita, can run in both offline and online modes and produces maps which can effectively handle a wide variety of road and intersection shapes. I will also discuss the limitations of fully automatic road network inference and describe our plans to tackle them.