Map Construction and Comparison

Motivation

In today’s society, there is an over-abundance of data. In particular, the movement of every cell phone carried by a person walking or every vehicle driven through a city can be traced by GPS and then recorded. Given the GPS trajectories of, for example, all taxis driving through a major city, I investigate how to synthesize the overabundance of information that these trajectories provide. One way of synthesizing the set of trajectories is to use them to estimate the underlying road network. This is called map (re-)construction. I focus on evaluating map construction algorithms. Given two road networks, A and B, represented as graphs embedded in a compact subspace of R^2, the task is to compute a meaningful distance between the two road networks that takes into consideration both the local and the global differences. For example, A may be the ground truth road network and B may be the road network reconstructed from GPS trajectory data. Moreover, this research applies to more networks than just to road networks. For example, one may also consider biological networks, filaments of galaxies throughout the universe, and hiking paths.

Publications and Preprints

Presentations

  • Local Homology Based Distance [Slides]