Multi-User Mobile Sequential Recommendation: An Efficient Parallel Computing Paradigm

ABSTRACT

The classic mobile sequential recommendation (MSR) problem aims to provide the optimal route to taxi drivers for minimizing the potential travel distance before they meet next passengers. However, the problem is designed from the view of a single user and may lead to overlapped recommendations and cause traffic problems. Existing approaches usually contain an offline pruning process with extremely high computational cost, given a large number of pick-up points. To this end, we formalize a new multi-user MSR (MMSR) problem that locates optimal routes for a group of drivers with different starting positions. We develop two efficient methods, PSAD and PSAD-M, for solving the MMSR problem by ganging parallel computing and simulated annealing. Our methods outperform several existing approaches, especially for high-dimensional MMSR problems, with a record-breaking performance of 180x speedup using 384 cores.

References

1. David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William J. Cook. 2011. The traveling salesman problem: a computational study. Princeton university press.
2. RaúL BañOs, Julio Ortega, Consolación Gil, Antonio FernáNdez, and Francisco De Toro. 2013. A simulated annealing-based parallel multi-objective approach to vehicle routing problems with time windows. Expert Systems with Applications 40, 5 (2013), 1696--1707.
3. King-Wai Chu, Yuefan Deng, and John Reinitz. 1999. Parallel simulated annealing by mixing of states. J. Comput. Phys. 148, 2 (1999), 646--662.
4. George B Dantzig and John H Ramser. 1959. The truck dispatching problem. Management Science 6, 1 (1959), 80--91.
5. Frederica Darema, Scott Kirkpatrick, and V. Alan Norton. 1987. Parallel algorithms for chip placement by simulated annealing. IBM Journal of Research and Development 31, 3 (1987), 391--402.
6. Frank J Fabozzi and Keli Xiao. 2017. Explosive rents: The real estate market dynamics in exuberance. The Quarterly Review of Economics and Finance 66 (2017), 100--107.
7. Frank J Fabozzi and Keli Xiao. 2018. The Timeline Estimation of Bubbles: The Case of Real Estate. Real Estate Economics (2018).
8. Yong Ge, Chuanren Liu, Hui Xiong, and Jian Chen. 2011. A taxi business intelligence system. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 735--738.
9. Yong Ge, Hui Xiong, Alexander Tuzhilin, Keli Xiao, Marco Gruteser, and Michael Pazzani. 2010. An energy--efficient mobile recommender system. In Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. 899--908.
10. Jianbin Huang, Xuejun Huangfu, Heli Sun, Hui Li, Peixiang Zhao, Hong Cheng, and Qinbao Song. 2015. Backward path growth for efficient mobile sequential recommendation. IEEE Transactions on Knowledge and Data Engineering 27, 1 (2015), 46--60.
11. Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. 1983. Optimization by simulated annealing. Science 220 (1983), 671--680.
12. Chuanren Liu, Yong Ge, Hui Xiong, Keli Xiao, Wei Geng, and Matt Perkins. 2014. Proactive workflow modeling by stochastic processes with application to healthcare operation and management. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 1593-- 1602.
13. Chuanren Liu, Hui Xiong, Spiros Papadimitriou, Yong Ge, and Keli Xiao. 2017. A proactive workflow model for healthcare operation and management. IEEE transactions on knowledge and data engineering 29, 3 (2017), 586--598.
14. Zhihao Lou and John Reinitz. 2016. Parallel simulated annealing using an adaptive resampling interval. Parallel computing 53 (2016), 23--31.
15. Shuo Ma, Yu Zheng, and Ouri Wolfson. 2013. T-share: A large-scale dynamic taxi ridesharing service. In The 2013 IEEE 29th International Conference on Data Engineering (ICDE). 410--421.
16. Shuo Ma, Yu Zheng, and OuriWolfson. 2015. Real-time city-scale taxi ridesharing. IEEE Transactions on Knowledge and Data Engineering 27, 7 (2015), 1782--1795.
17. SamirWMahfoud and David E Goldberg. 1995. Parallel recombinative simulated annealing: a genetic algorithm. Parallel computing 21, 1 (1995), 1--28.
18. Jason W Powell, Yan Huang, Favyen Bastani, and Minhe Ji. 2011. Towards reducing taxicab cruising time using spatio-temporal profitability maps. In International Symposium on Spatial and Temporal Databases. Springer, 242--260.
19. Meng Qu, Hengshu Zhu, Junming Liu, Guannan Liu, and Hui Xiong. 2014. A cost-effective recommender system for taxi drivers. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. 45--54.
20. Andrew Sohn. 1996. Generalized speculative computation of parallel simulated annealing. Annals of Operations Research 63, 1 (1996), 29--55.
21. Paolo Toth and Daniele Vigo. 2002. The vehicle routing problem. SIAM.
22. RanWang, Chi-Yin Chow, Yan Lyu, Victor CS Lee, Sam Kwong, Yanhua Li, and Jia Zeng. 2018. Taxirec: recommending road clusters to taxi drivers using rankingbased extreme learning machines. IEEE Transactions on Knowledge and Data Engineering 30, 3 (2018), 585--598.
23. Keli Xiao, Qi Liu, Chuanren Liu, and Hui Xiong. 2018. Price Shock Detection With an Influence-Based Model of Social Attention. ACM Transactions on Management Information Systems 9, 1 (2018), 2.
24. Zeyang Ye, Keli Xiao, and Yuefan Deng. 2015. Investigation of Simulated Annealing Cooling Schedule for Mobile Recommendations. In Proceedings of the 2015 IEEE International Conference on Data Mining Workshop (ICDMW). IEEE, 1078--1084.
25. Zeyang Ye, Keli Xiao, Yong Ge, and Yuefan Deng. 2018. Applying Simulated Annealing and Parallel Computing to the Mobile Sequential Recommendation. IEEE Transactions on Knowledge and Data Engineering (2018).
26. Jing Yuan, Yu Zheng, Liuhang Zhang, Xing Xie, and Guangzhong Sun. 2011. Where to find my next passenger. In Proceedings of the 13th international conference on Ubiquitous computing. 109--118.
27. Nicholas Jing Yuan, Yu Zheng, Liuhang Zhang, and Xing Xie. 2013. T-finder: A recommender system for finding passengers and vacant taxis. IEEE Transactions on Knowledge and Data Engineering 25, 10 (2013), 2390--2403.
28. Li Zhang, Keli Xiao, Qi Liu, Yefan Tao, and Yuefan Deng. 2015. Modeling social attention for stock analysis: An influence propagation perspective. In Proceedings of the 2015 IEEE International Conference on Data Mining (ICDM). IEEE, 609--618.
29. Hengshu Zhu, Enhong Chen, Kuifei Yu, Huanhuan Cao, Hui Xiong, and Jilei Tian. 2012. Mining personal context-aware preferences for mobile users. In Proceedings of the 2012 IEEE International Conference on Data Mining (ICDM). IEEE, 1212--1217.

Index Terms

• Computing methodologies

  • Parallel computing methodologies

• Information systems

  • Information systems applications

    • Data mining

    • Mobile information processing systems