基于用户偏好的最优路径搜索

doi:10.3969/j.issn.1000-5641.2019.05.008

华东师范大学学报(自然科学版) ›› 2019, Vol. 2019 ›› Issue (5): 100-112.doi: 10.3969/j.issn.1000-5641.2019.05.008

• 新兴应用中的计算机智能 • 上一篇下一篇

基于用户偏好的最优路径搜索

江群¹, 戴戈南¹, 张森¹, 葛又铭¹, 刘玉葆^1,2

1. 中山大学数据科学与计算机学院, 广州 510006;
2. 中山大学广东省大数据分析与处理重点实验室, 广州 510006

收稿日期:2019-07-29 出版日期:2019-09-25 发布日期:2019-10-11
通讯作者: 刘玉葆,男,教授,博士生导师,研究方向为数据库与数据挖掘.E-mail:liuyubao@mail.sysu.edu.cn. E-mail:liuyubao@mail.sysu.edu.cn
作者简介:江群,女,硕士研究生,研究方向为数据库与数据挖掘.E-mail:2739670944@qq.com.
基金资助:
国家自然科学基金（U1501252，61572537）

Optimal route search based on user preferences

JIANG Qun¹, DAI Ge-nan¹, ZHANG Sen¹, GE You-ming¹, LIU Yu-bao^1,2

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:2019-07-29 Online:2019-09-25 Published:2019-10-11

摘要/Abstract

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

关键词: 路径搜索, 用户偏好, A^*算法

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

中图分类号:

TP311.13

江群, 戴戈南, 张森, 葛又铭, 刘玉葆. 基于用户偏好的最优路径搜索[J]. 华东师范大学学报(自然科学版), 2019, 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 Sc, 2019, 2019(5): 100-112.

参考文献

[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.

基于用户偏好的最优路径搜索

Optimal route search based on user preferences

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	孔超, 钱卫宁, 周傲英. NoSQL系统的容错机制：原理与系统示例[J]. 华东师范大学学报(自然科学版), 2014, 2014(5): 1-16.
[2]	裴欧亚, 刘文洁, 李战怀, 田征. 一种面向海量分布式数据库的嵌套查询策略[J]. 华东师范大学学报(自然科学版), 2014, 2014(5): 271-280.
[3]	景寒星;陈少红;俞琨. 自动抽取web数据的树对齐算法[J]. 华东师范大学学报(自然科学版), 2010, 2010(5): 96-102.
[4]	王路帮. BCDM中的时间标签规范及优化[J]. 华东师范大学学报(自然科学版), 2006, 2006(5): 110-115.
[5]	王路帮. BCDM中的时间标签规范及优化[J]. 华东师范大学学报(自然科学版), 2006, 2006(5): 110-115.