Finding time period-based most frequent path in big trajectory data

Wuman Luo, Haoyu Tan, Lei Chen, Lionel M. Ni

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

186 Citations (Scopus)

Abstract

The rise of GPS-equipped mobile devices has led to the emergence of big trajectory data. In this paper, we study a new path finding query which finds the most frequent path (MFP) during user-specified time periods in large-scale historical trajectory data. We refer to this query as time period-based MFP (TPMFP). Specifically, given a time period T, a source vs and a destination vd, TPMFP searches the MFP from vs to v d during T. Though there exist several proposals on defining MFP, they only consider a fixed time period. Most importantly, we find that none of them can well reflect people's common sense notion which can be described by three key properties, namely suffix-optimal (i.e., any suffix of an MFP is also an MFP), length-insensitive (i.e., MFP should not favor shorter or longer paths), and bottleneck-free (i.e., MFP should not contain infrequent edges). The TPMFP with the above properties will reveal not only common routing preferences of the past travelers, but also take the time effectiveness into consideration. Therefore, our first task is to give a TPMFP definition that satisfies the above three properties. Then, given the comprehensive TPMFP definition, our next task is to find TPMFP over huge amount of trajectory data efficiently. Particularly, we propose efficient search algorithms together with novel indexes to speed up the processing of TPMFP. To demonstrate both the effectiveness and the efficiency of our approach, we conduct extensive experiments using a real dataset containing over 11 million trajectories.

Original languageEnglish
Title of host publicationSIGMOD 2013 - International Conference on Management of Data
Pages713-724
Number of pages12
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event2013 ACM SIGMOD Conference on Management of Data, SIGMOD 2013 - New York, NY, United States
Duration: 22 Jun 201327 Jun 2013

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Conference

Conference2013 ACM SIGMOD Conference on Management of Data, SIGMOD 2013
Country/TerritoryUnited States
CityNew York, NY
Period22/06/1327/06/13

Keywords

  • Big trajectory data
  • Path finding

Fingerprint

Dive into the research topics of 'Finding time period-based most frequent path in big trajectory data'. Together they form a unique fingerprint.

Cite this