Effective and Efficient Reuse of Past Travel Behavior for Route Recommendation

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

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

4 Citationer (Scopus)

Abstrakt

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.
OriginalsprogEngelsk
TitelKDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Antal sider11
ForlagAssociation for Computing Machinery
Publikationsdato2019
Sider488-498
ISBN (Trykt)9781450362016
ISBN (Elektronisk)9781450362016
DOI
StatusUdgivet - 2019
BegivenhedACM Conference on Knowledge Discovery and Data Mining - Anchorage, USA
Varighed: 4 aug. 20198 aug. 2019
Konferencens nummer: 25th

Konference

KonferenceACM Conference on Knowledge Discovery and Data Mining
Nummer25th
LandUSA
ByAnchorage
Periode04/08/201908/08/2019

    Fingerprint

Citationsformater

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. I KDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (s. 488-498). Association for Computing Machinery. https://doi.org/10.1145/3292500.3330835