Using Incomplete Information for Complete Weight Annotation of Road Networks

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

  • Bin Yang, Danmark
  • Manohar Kaul, Danmark
  • Christian S. Jensen, Aalborg Universitet, Danmark
We are witnessing increasing interests in the effective use of road networks. It is a precondition to using a graph model for routing that all edges have weights. Weights that capture travel times and GHG emissions can be extracted from GPS trajectory data collected from the network. However, GPS trajectory data typically lack the coverage needed to assign weights to all edges. This paper formulates and addresses the problem of annotating all edges in a road network with travel cost based weights from a set of trips in the network that cover only a small fraction of the edges, each with an associated ground-truth travel cost. A general framework is proposed to solve the problem. Specifically, the problem is modeled as a regression problem and solved by minimizing a judiciously designed objective function that takes into account the topology of the road network. In particular, the use of weighted PageRank values of edges is explored for assigning appropriate weights to all edges, and the property of directional adjacency of edges is also taken into account to assign weights. Empirical studies with weights capturing travel time and GHG emissions on two road networks offer insight into the design properties of the proposed techniques and offer evidence that the techniques are effective.
TidsskriftI E E E Transactions on Knowledge & Data Engineering
Sider (fra-til)1267-1279
Antal sider13
StatusUdgivet - 2014


  • Correlation and regression analysis, Data mining, Database Applications, Database Management, Information Technology and Systems, Mathematics of Computing, Probability and Statistics, Spatial databases and GIS

Se relationer på Aarhus Universitet Citationsformater

ID: 54528716