Optimal route search based on user preferences

doi:10.3969/j.issn.1000-5641.2019.05.008

Abstract

Abstract: This paper studies the methodology for optimal route search based on user preferences, such as keyword and weight preferences, under a constraint. The research problem is NP-hard. To solve the query efficiently, we propose two new index building methods and select candidate nodes for retrieving the established indices. This paper subsequently proposes an A^* based route search algorithm to identify the optimal route and use several effective pruning strategies to speed up execution. Experimental results on two real-world check-in datasets demonstrates the effectiveness of the proposed method. When the budget ranges from 4 hours to 7 hours, our algorithm performs better than the state-of-the-art PACER algorithm.

Key words: route search, users' preferences, A^* algorithm

CLC Number:

TP311.13

JIANG Qun, DAI Ge-nan, ZHANG Sen, GE You-ming, LIU Yu-bao. Optimal route search based on user preferences[J]. Journal of East China Normal University(Natural Sc, 2019, 2019(5): 100-112.

References

[1] JUNGLAS I A, WATSON R T. Location-based services[J]. Communications of The ACM, 2008, 51(3):65-69.
[2] JIANG Q, TENG W, LIU Y. ORSUP:Optimal route search with users' preferences[C]//MDM, 2019:357-358.
[3] SHARIFZADEH M, KOLAHDOUZAN M R, SHAHABI C, et al. The optimal sequenced route query[J]. Very Large Data Bases, 2008, 17(4):765-787.
[4] LI F, CHENG D, HADJIELEFTHERIOU M, et al. On trip planning queries in spatial databases[C]//Proceedings of the 9th International Symposium on Spatial and Temporal Databases (SSTD'05), 2005:273-290.
[5] CHEN H, KU W, SUN M, et al. The multi-rule partial sequenced route query[C]//Advances in Geographic Information Systems, 2008:1-10.
[6] KANZA Y, LEVIN R, SAFRA E, et al. Interactive route search in the presence of order constraints[J]. Very Large Data Bases, 2010, 3(1):117-128.
[7] LI J, YANG Y D, MAMOULIS N, et al. Optimal route queries with arbitrary order constraints[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(5):1097-1110.
[8] 金鹏飞,牛保宁,张兴忠.高效的多关键词匹配最优路径查询算法KSRG[J].计算机应用, 2017, 37(2):352-359.
[9] LIU H, JIN C, YANG B, et al. Finding Top-k Optimal Sequenced Routes[C]//International Conference on Data Engineering, 2018:569-580.
[10] 鲍金玲,杨晓春.一种支持约束关系的高效的行程规划算法[J].小型微型计算机系统, 2013, 34(12):2702-2707.
[11] 吴澎,朱家明.基于多目标规划和智能优化算法的旅游线路设计研究[J].数学的实践与认识, 2016, 46(15):105-114.
[12] CAO X, CHEN L, CONG G, et al. Keyword-aware optimal route search[J]. Very Large Data Bases, 2012, 5(11):1136-1147.
[13] LIU H, JIN C, YANG B, et al. Finding Top-k Shortest Paths with Diversity[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(3):488-502.
[14] LIANG H, WANG K. Top-k Route Search through Submodularity Modeling of Recurrent POI Features[C]//International Acm Sigir Conference on Research and Development in Information Retrieval, 2018:545-554.
[15] CHEKURI C S, PAL M. A recursive greedy algorithm for walks in directed graphs[C]//Foundations of Computer Science, 2005:245-253.
[16] ZENG Y, CHEN X, CAO X, et al. Optimal route search with the coverage of users' preferences[C]//International Conference on Artificial Intelligence, 2015:2118-2124.
[17] DAI J, YANG B, GUO C, et al. Personalized route recommendation using big trajectory data[C]//International Conference on Data Engineering, 2015:543-554.
[18] ELARINI K, VEDA G, SHAHAF D, et al. Turning down the noise in the blogosphere[C]//Knowledge Discovery and Data Mining, 2009:289-298.
[19] KEMPE D, KLEINBERG J M, TARDOS E, et al. Maximizing the spread of influence through a social network[C]//Knowledge Discovery and Data Mining, 2003:137-146.
[20] LESKOVEC J, KRAUSE A, GUESTRIN C, et al. Cost-effective outbreak detection in networks[C]//Knowledge Discovery and Data Mining, 2007:420-429.
[21] YUAN Q, CONG G, MA Z, et al. Time-aware point-of-interest recommendation[C]//International Acm Sigir Conference on Research and Development in Information Retrieval, 2013:363-372.
[22] CHO E, MYERS S A, LESKOVEC J, et al. Friendship and mobility:user movement in location-based social networks[C]//Proceedings of the 17th ACM SIGKDD International Conference, 2011:1082-1090.