本文研究基于用户偏好的最优路径搜索，在预算约束下寻找一条满足用户偏好即关键字和权重偏好的最优路径.此研究问题是NP-hard.为了高效地解决这类查询问题，本文提出新的索引建立方法，在查询阶段利用索引结构过滤出候选节点集.另外，提出基于A*的路径搜索算法来做路径查询，并利用几个有效的剪枝策略加快算法的执行速度.在两个真实的签到数据集上的实验结果证明了本文提出方法的有效性.当预算时间设置为4~7h时，与已有最好的PACER算法相比，本文的路径搜索算法消耗的查询时间更短.
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.
[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.
中国综合性科技类核心期刊(北大核心)