Effective and efficient reuse of past travel behavior for route recommendation

Lisi Chen, Shuo Shang*, Christian S. Jensen, Bin Yao, Zhiwei Zhang, Ling Shao

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

57 Citations (Scopus)

Abstract

With the increasing availability of moving-object tracking data, use of this data for route search and recommendation is increasingly important. To this end, we propose a novel parallel split-and-combine approach to enable route search by locations (RSL-Psc). Given a set of routes, a set of places to visit O, and a threshold ?, we retrieve the route composed of sub-routes that (i) has similarity to O no less than ? and (ii) contains the minimum number of sub-route combinations. The resulting functionality targets a broad range of applications, including route planning and recommendation, ridesharing, and location-based services in general. To enable efficient and effective RSL-Psc computation on massive route data, we develop novel search space pruning techniques and enable use of the parallel processing capabilities of modern processors. Specifically, we develop two parallel algorithms, Fully-Split Parallel Search (FSPS) and Group-Split Parallel Search (GSPS). We divide the route split-and-combine task into kM=0 S(|O|, k + 1) sub-tasks, where M is the maximum number of combinations and S(·) is the Stirling number of the second kind. In each sub-task, we use network expansion and exploit spatial similarity bounds for pruning. The algorithms split candidate routes into sub-routes and combine them to construct new routes. The sub-tasks are independent and are performed in parallel. Extensive experiments with real data offer insight into the performance of the algorithms, indicating that our RSL-Psc problem can generate high-quality results and that the two algorithms are capable of achieving high efficiency and scalability.

Original languageEnglish
Title of host publicationKDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
PublisherAssociation for Computing Machinery (ACM)
Pages488-498
Number of pages11
ISBN (Electronic)9781450362016
DOIs
Publication statusPublished - 25 Jul 2019
Event25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019 - Anchorage, United States
Duration: 4 Aug 20198 Aug 2019

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Conference

Conference25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019
Country/TerritoryUnited States
CityAnchorage
Period4/08/198/08/19

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

  • Route recommendation
  • Trajectory search

Fingerprint

Dive into the research topics of 'Effective and efficient reuse of past travel behavior for route recommendation'. Together they form a unique fingerprint.

Cite this