D. Chen, L. Guibas, J. Hershberger, and J. Sun, Road Network Reconstruction for Organizing Paths, ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.

Abstract:

We consider the problem of reconstructing a road network from a collection of path traces and provide guarantees to the accuracy of the reconstruction under reasonable assumptions. Our algorithm can be used to process a collection of polygonal paths in the plane so that shared structures (subpaths) among the paths in the collection can be discovered and the collection can be organized to allow efficient path similarity queries against new query paths on the same road network. This is a timely problem, as GPS or other location traces of both people and vehicles are becoming available in a large scale and there is a real need to create appropriate data structures and data bases for such data.

Bibtex: 

@inproceedings{cghs-rnrop-10,
       author = {Daniel Chen, Leonidas Guibas, John Hershberger, and Jian Sun},
       title = {Road network reconstruction for organizing paths},
       booktitle = {Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (to appear)},
      year = {2010}
}