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

江群; 戴戈南; 张森; 葛又铭; 刘玉葆

doi:10.3969/j.issn.1000-5641.2019.05.008

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

doi: 10.3969/j.issn.1000-5641.2019.05.008

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

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

基金项目:

国家自然科学基金 U1501252

国家自然科学基金 61572537

详细信息

作者简介:
江群, 女, 硕士研究生, 研究方向为数据库与数据挖掘.E-mail:2739670944@qq.com

通讯作者:
刘玉葆, 男, 教授, 博士生导师, 研究方向为数据库与数据挖掘.E-mail:liuyubao@mail.sysu.edu.cn

中图分类号: TP311.13
计量
- 文章访问数: 193
- HTML全文浏览量: 120
- PDF下载量: 0
- 被引次数: 0
出版历程
- 收稿日期: 2019-07-29
- 刊出日期: 2019-09-25

Optimal route search based on user preferences

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

摘要

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

HTML全文

图 1 POI地图示例

Fig. 1 A POI map

下载: 全尺寸图片幻灯片

图 2 POI地图的最小代价矩阵索引

Fig. 2 Minimum cost matrix index of the POI map

下载: 全尺寸图片幻灯片

图 3 POI地图的关键字反向索引

Fig. 3 Keyword inverted index of the POI map

下载: 全尺寸图片幻灯片

图 4 预算代价对运行时间的影响

Fig. 4 Impact of budget on runtime

下载: 全尺寸图片幻灯片

图 5 预算代价对搜索空间的影响

Fig. 5 Impact of budget on search space

下载: 全尺寸图片幻灯片

图 6 关键字数量对运行时间的影响

Fig. 6 Impact of $\vert $K$\vert $ on runtime

下载: 全尺寸图片幻灯片

图 7 查询$Q_1$的路径结果$R_1$

Fig. 7 Query result $R_1$ of $Q_1$

下载: 全尺寸图片幻灯片

图 8 查询$Q_2$的路径结果$R_2$

Fig. 8 Query result $R_2$ of $Q_2$

下载: 全尺寸图片幻灯片

表 1 符号及其含义

Tab. 1 Nomenclature

符号	含义
$s(v_i)$	停留兴趣点$v_i$产生的代价
$SC_{k_q}(v_i)$	关键字$k_q$在兴趣点$v_i$处的评分
$T(v_i, v_j)$	$(v_i$, $v_j)$边代价
$T_{sm} (v_i, v_j)$	$(v_i$, $v_j)$边最小代价
$cost(R)$	路径$R$的代价
$Gain(R)$	路径$R$的收益
$Q=(v_s, v_t, K, \Upsilon, \Delta)$	$v_s$为起点, $v_t$为终点, $K$为查询关键字集, $\Upsilon$为关键字权重集, $\Delta$为预算约束
$V_Q$	查询$Q$的候选节点集
$R_i^k$	从$v_s$到$v_i$的第$k$条路径
$L_i^k$	从$v_s$到$v_i$的第$k$条路径的标签

下载: 导出CSV

算法1 基于A*的路径搜索算法

输入:查询$Q =(v_s, v_t, K, \Upsilon, \Delta)$, 图$G=(V_Q, E)$, 最小代价矩阵索引$T_{sm}$, 停留时间列表$s$

输出:最优路径R

1: 初始化一个最大优先队列Q;

2: $R=\varnothing$, $Gain_{\max}= -\infty$, $BS_{\min}= +\infty$;

3: 创建路径标签$L_s^0=\langle(v_s), 0, 0, 0\rangle$;

4: Q.enqueue $(L_s^0)$;

5: $\textbf{While}$ Q不为空 do

6: {

7: $L_i^k=$Q.dequeue;

8: If $L_i^k.f^i (R_{s \to t})\leqslant Gain_{\max}$ then

9: Break;

10: 从路径标签$L_i^k$中取出路径$R_i^k$;

11: 新的候选节点集CandiSet=$V_Q\setminus V_{R_i^k}$;

12: For $v_j$ in CandiSet do

13: {

14: 创建一条路径$R_j^l=R_i^k\cup\{v_j\}$;

15: $cost(R_j^l) = L_i^k.cost(R_i^k) +T_{sm} (v_i, v_j) +s(v_j)$;

16: $finalCost = cost(R_j^l)+T_{sm}(v_j, v_t)$;

17: If $finalCost>{\it\Delta} $ then

18: Continue;

19: 计算路径收益$Gain(R_j^l)$;

20: If $Gain(R_j^l)>Gain_{\max}$ then

21: {

22: $R = R_j^l\cup\{v_t\}$;

23: $Gain_{\max}= Gain(R_j^l)$;

24: $BS_{\min}=finalCost$;

25: }

26: If$Gain(R_j^l)==Gain_{\max}$ $and$ $finalCost < BS_{\min}$ then

27: {

28: $R =R_j^l\cup\{v_t\}$;

29: $BS_{\min}= finalCost$;

30: }

31: 估计收益上界$f^j(R_{s\to t})$;

32: If $f^j (R_{s\to t})\geqslant Gain_{\max}$ then

33: {

34: 创建路径标签$L_l^j = \langle R_l^j, cost(R_l^j), Gain(R_l^j), f^j (R_{s\to t}))\rangle; $

35: Q.enqueue($L_l^j)$;

36: }

37: }

38: }

39: return $R$;

下载: 导出CSV

表 2 数据集的描述性统计信息

Tab. 2 Descriptive statistics of datasets

数据集	兴趣点个数	边数	平均路程时间	关键字个数
SG	1 625	24 969	16.24 min	202
AS	2 609	34 340	11.12 min	252

下载: 导出CSV

参考文献(22)

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