Optimal route search based on user preferences

JIANG Qun; DAI Ge-nan; ZHANG Sen; GE You-ming; LIU Yu-bao

doi:10.3969/j.issn.1000-5641.2019.05.008

Issue 5

Dec. 2019

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2019 > (5): 100-112

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 Sciences), 2019, (5): 100-112. doi: 10.3969/j.issn.1000-5641.2019.05.008

Citation:

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 Sciences), 2019, (5): 100-112. doi: 10.3969/j.issn.1000-5641.2019.05.008

Citation:

PDF( 1712 KB)

Optimal route search based on user preferences

doi: 10.3969/j.issn.1000-5641.2019.05.008

1.
School of Data and Computer Science, Sun Yat-Sen University, Guangzhou 510006, China
2.
Guangdong Key Laboratory of Big Data Analysis and Processing, Sun Yat-Sen University, Guangzhou 510006, China

Received Date: 2019-07-29
Publish Date: 2019-09-25

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.
- route search,
- users' preferences,
- A^* algorithm

FullText(HTML)

References(22)

References

[1]	JUNGLAS I A, WATSON R T. Location-based services[J]. Communications of The ACM, 2008, 51(3):65-69. http://d.old.wanfangdata.com.cn/Periodical/jsjxb201107001
[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. doi: 10.1007/s00778-006-0038-6
[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. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=CC0211524625
[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. doi: 10.1109/TKDE.2012.36
[8]	金鹏飞, 牛保宁, 张兴忠.高效的多关键词匹配最优路径查询算法KSRG[J].计算机应用, 2017, 37(2):352-359. http://d.old.wanfangdata.com.cn/Periodical/jsjyy201702009
[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. doi: 10.3969/j.issn.1000-1220.2013.12.009
[11]	吴澎, 朱家明.基于多目标规划和智能优化算法的旅游线路设计研究[J].数学的实践与认识, 2016, 46(15):105-114. http://d.old.wanfangdata.com.cn/Periodical/sxdsjyrs201615013
[12]	CAO X, CHEN L, CONG G, et al. Keyword-aware optimal route search[J]. Very Large Data Bases, 2012, 5(11):1136-1147. http://d.old.wanfangdata.com.cn/NSTLHY/NSTL_HYCC0214917024/
[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. doi: 10.1109/TKDE.2017.2773492
[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.