Effective and Efficient Reuse of Past Travel Behavior for Route Recommendation

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

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

2 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 ∑k=0 M 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
Number of pages11
PublisherAssociation for Computing Machinery
Publication date2019
Pages488-498
ISBN (Print)9781450362016
ISBN (Electronic)9781450362016
DOIs
Publication statusPublished - 2019
EventACM Conference on Knowledge Discovery and Data Mining - Anchorage, United States
Duration: 4 Aug 20198 Aug 2019
Conference number: 25th

Conference

ConferenceACM Conference on Knowledge Discovery and Data Mining
Number25th
CountryUnited States
CityAnchorage
Period04/08/201908/08/2019

    Fingerprint

Keywords

  • Route recommendation
  • Trajectory search

Cite this

Chen, L., Shang, S., Jensen, C. S., Yao, B., Zhang, Z., & Shao, L. (2019). Effective and Efficient Reuse of Past Travel Behavior for Route Recommendation. In KDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 488-498). Association for Computing Machinery. https://doi.org/10.1145/3292500.3330835