TORD Problem and Its Solution Based on Big Trajectories Data

Identifying a preferable route is an important problem in location-based service. A user may want to find “an optimal route such that it passes by mall, restaurant, and bank, meanwhile go through bank before mall, and arrive at the restaurant at mealtime.” However, none of the algorithms in the existing work on route planning can be used to answer such queries that exist in real life. Motivated by this, the authors define the problem of temporal-sensitive optimal route discovery (TORD), which is an NP-hard problem. Since the rise of GPS-equipped mobile devices has led to the emergence of big trajectory data, they propose a hybrid evaluation indicator of routes called preference combined by the distance from the road network and popularity from trajectories. To achieve this goal, the authors first develop an improved compact minimum bound rectangle algorithm to get the association between trajectory data and road network, which can update the association conveniently for new trajectories. Then, they construct a two-layer preference network that is used for mining the preference and travel time. Finally, they devise three approximation algorithms to answer TORD queries. The results of empirical studies show that all the proposed algorithms are capable of answering TORD queries efficiently.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01603705
  • Record Type: Publication
  • Files: TLIB, TRIS
  • Created Date: May 31 2016 1:42PM