TY - GEN
T1 - Effective and efficient reuse of past travel behavior for route recommendation
AU - Chen, Lisi
AU - Shang, Shuo
AU - Jensen, Christian S.
AU - Yao, Bin
AU - Zhang, Zhiwei
AU - Shao, Ling
N1 - Funding Information:
Acknowledgements: This work (Bin Yao) was supported by the NSFC (61872235, 61729202, 61832017, U1636210) and the National Key Research and Development Program of China (2018YFC1504504). Additionally, Zhiwei Zhang is supported by GRF (12201518, 12232716, 12258116) and NSFC (61602395).
PY - 2019/7/25
Y1 - 2019/7/25
N2 - 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.
AB - 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.
KW - Route recommendation
KW - Trajectory search
UR - http://www.scopus.com/inward/record.url?scp=85068856354&partnerID=8YFLogxK
U2 - 10.1145/3292500.3330835
DO - 10.1145/3292500.3330835
M3 - Conference proceeding
AN - SCOPUS:85068856354
T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
SP - 488
EP - 498
BT - KDD 2019 - Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
PB - Association for Computing Machinery (ACM)
T2 - 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2019
Y2 - 4 August 2019 through 8 August 2019
ER -