计算机科学技术学报 ›› 2019,Vol. 34 ›› Issue (4): 818-838.doi: 10.1007/s11390-019-1944-6

所属专题： Data Management and Data Mining

• Data Management and Data Mining • 上一篇    下一篇

空间多样化的top-k路线

Hong-Fei Xu1, Student Member, CCF, Yu Gu1, Senior Member, CCF Jian-Zhong Qi2, Member, ACM, Jia-Yuan He2, Ge Yu1,*, Fellow, CCF, Member, ACM, IEEE   

  1. 1 College of Computer Science and Engineering, Northeastern University, Shenyang 110169, China;
    2 Department of Computing and Information Systems, The University of Melbourne, Melbourne, VIC 3010, Australia
  • 收稿日期:2018-05-15 修回日期:2019-05-15 出版日期:2019-07-11 发布日期:2019-07-11
  • 通讯作者: Ge Yu E-mail:yuge@mail.neu.edu.cn
  • 作者简介:Hong-Fei Xu received his M.E.degree in computer science from Shenyang Jianzhu University,Shenyang,in 2014.He is currently a Ph.D.candidate in computer software and theory at Northeastern University,Shenyang.His research interests include spatial data management and data mining.
  • 基金资助:
    This work was supported by the National Key Research and Development Program of China under Grant No. 2018YFB1003404, the National Natural Science Foundation of China under Grant Nos. 61872070, U1435216, U1811261, and 61602103, and the Fundamental Research Funds for the Central Universities of China under Grant No. N171605001.

Diversifying Top-k Routes with Spatial Constraints

Hong-Fei Xu1, Student Member, CCF, Yu Gu1, Senior Member, CCF Jian-Zhong Qi2, Member, ACM, Jia-Yuan He2, Ge Yu1,*, Fellow, CCF, Member, ACM, IEEE   

  1. 1 College of Computer Science and Engineering, Northeastern University, Shenyang 110169, China;
    2 Department of Computing and Information Systems, The University of Melbourne, Melbourne, VIC 3010, Australia
  • Received:2018-05-15 Revised:2019-05-15 Online:2019-07-11 Published:2019-07-11
  • Contact: Ge Yu E-mail:yuge@mail.neu.edu.cn
  • Supported by:
    This work was supported by the National Key Research and Development Program of China under Grant No. 2018YFB1003404, the National Natural Science Foundation of China under Grant Nos. 61872070, U1435216, U1811261, and 61602103, and the Fundamental Research Funds for the Central Universities of China under Grant No. N171605001.

PDF (PC)

148

补充材料

1

随着基于位置的社交网络中签到数据的快速增长，旅游路线推荐问题受到越来越多的关注。现有的研究大多集中于如何返回具有高流行度的出行路线。本文通过考虑空间多样化因素，进一步提高路线推荐结果的可用性。本文提出一种新的查询问题，称为"空间多样化的top-k路线"查询。该查询返回k条高流行度的路线。每条路线从给定起始点出发，满足时间约束代价，并且包含指定类别的POI点。此外，返回的结果中任意两条路线之间的距离大于给定的距离约束。我们证明了该查询问题为NP-hard。针对该问题，本文提出了两个准确算法：第一个算法首先找到满足查询约束的所有候选路线，之后找到满足距离约束且具有最高流行度的k条路线；第二个算法在寻找候选路线的同时逐步构建最优路线组合。此外，为了获得更高的查询效率，本文提出了一个具有近似率保证的近似算法。我们使用真实数据集验证了所提出算法的效率和有效性。实验结果表明，本文提出的算法能够找到包含不同空间位置的POI的高流行路线。相较于基本算法，近似算法最多可节省90%的运行时间。

关键词: 旅游路线推荐, 空间多样性, 路线搜索, 签到数据

Abstract: Trip recommendation has become increasingly popular with the rapid growth of check-in data in locationbased social networks. Most existing studies focused only on the popularity of trips. In this paper, we consider further the usability of trip recommendation results through spatial diversification. We thereby formulate a new type of queries named spatial diversified top-k routes (SDkR) query. This type of queries finds k trip routes with the highest popularity, each of which starts at a given starting point, consumes travel time within a given time budget, and passes through points of interest (POIs) of given categories. Any two trip routes returned are diversified to a certain degree defined by the spatial distance between the two routes. We show that the SDkR problem is NP-hard. We propose two precise algorithms to solve the problem. The first algorithm starts with identifying all candidate routes that satisfy the query constraints, and then searches for the k-route combination with the highest popularity. The second algorithm identifies the candidate routes and builds up the optimal k-route combination progressively at the same time. Further, we propose an approximate algorithm to obtain even higher query efficiency with precision bounds. We demonstrate the effectiveness and efficiency of the proposed algorithms on real datasets. Our experimental results show that our algorithms find popular routes with diversified POI locations. Our approximate algorithm saves up to 90% of query time compared with the baseline algorithms.

Key words: trip recommendation, spatial diversity, route search, check-in data

[1] Su H, Zheng K, Huang J M, Liu T Y, Wang H Z, Zhou X F. A crowd-based route recommendation system-CrowdPlanner. In Proc. the 30th International Conference on Data Engineering, March 2014, pp.1178-1181.
[2] Lu H C, Chen C Y, Tseng V S. Personalized trip recommendation with multiple constraints by mining user check-in behaviors. In Proc. the 20th International Conference on Advances in Geographic Information Systems, November 2012, pp.209-218.
[3] Zhang C Y, Liang H W, Wang K, Sun K L. Personalized trip recommendation with PoI availability and uncertain traveling time. In Proc. the 24th ACM International Conference on Information and Knowledge Management, October 2015, pp.911-920.
[4] Hsieh H P, Li C T. Mining and planning time-aware routes from check-in data. In Proc. the 23rd International Conference on Information and Knowledge Management, November 2014, pp.481-490.
[5] Shang S, Ding R G, Yuan B, Xie K X, Zheng K, Kalnis P. User oriented trajectory search for trip recommendation. In Proc. the 15th International Conference on Extending Database Technology, March 2012, pp.156-167.
[6] Dai J, Liu C F, Xu J J, Ding Z M. On personalized and sequenced route planning. World Wide Web:Internet and Web Information Systems, 2016, 19(4):679-705.
[7] Tang J Y, Sanderson M. Spatial diversity, do users appreciate it? In Proc. the 6th Workshop on Geographic Information Retrieval, February 2010, Article No. 22.
[8] Chen Z B, Shen H T, Zhou X F, Zheng Y, Xie X. Searching trajectories by locations:An efficiency study. In Proc. the 29th ACM SIGMOD International Conference on Management of Data, June 2010, pp.255-266.
[9] Shang S, Chen L S, Jensen C S, Wen J R, Kalnis P. Searching trajectories by regions of interest. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(7):1549-1562.
[10] Shang S, Ding R, Zheng K, Jensen C S, Kalnis P, Zhou X F. Personalized trajectory matching in spatial networks. The International Journal on Very Large Data Bases, 2014, 23(3):449-468.
[11] Zheng K, Zheng B L, Xu J J, Liu G F, An L, Li Z X. Popularity-aware spatial keyword search on activity trajectories. World Wide Web:Internet and Web Information Systems, 2017, 20(4):749-773.
[12] Zheng K, Yang Y, Shang S, Yuan N J. Towards efficient search for activity trajectories. In Proc. the 29th International Conference on Data Engineering, April 2013, pp.230-241.
[13] Shang S, Chen L S, Zheng K, Jensen C S, Wei Z, Kalnis P. Parallel trajectory-to-location join. IEEE Transactions on Knowledge and Data Engineering. doi:10.1109/TKDE.2018.2854705.
[14] Wei L Y, Zheng Y, Peng W C. Constructing popular routes from uncertain trajectories. In Proc. the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2012, pp.195-203.
[15] Cao X, Chen L S, Cong G, Xiao X K. Keyword-aware optimal route search. Proceedings of the VLDB Endowment, 2012, 5(11):1136-1147.
[16] Li Y J, Yang W D, Dan W, Xie Z P. Keyword-aware dominant route search for various user preferences. In Proc. the 20th International Conference on Database Systems for Advanced Applications, April 2015, pp.207-222.
[17] Shang S, Chen L S, Wei Z W, Jensen C S, Wen J R, Kalnis P. Collective travel planning in spatial networks. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(5):1132-1146.
[18] Wen Y T, Yeo J, Peng W C, Hwang S W. Efficient keywordaware representative travel route recommendation. IEEE Transactions on Knowledge and Data Engineering, 2018, 29(8):1639-1652.
[19] Liu H, Jin C Q, Yang B, Zhou A Y. Finding top-k optimal sequenced routes. In Proc. the 34th International Conference on Data Engineering, April 2018, pp.569-580.
[20] Shang S, Liu J, Zheng K, Lu H, Pedersen T B, Wen J R. Planning unobstructed paths in traffic-aware spatial networks. Geo Informatica, 2015, 19(4):723-746.
[21] Soma S C, Hashem T, Cheema M A, Samrose S. Trip planning queries with location privacy in spatial databases. World Wide Web:Internet and Web Information Systems, 2017, 20(2):205-236.
[22] Zheng B L, Su H, Hua W, Zheng K, Zhou X F, Li G H. Efficient clue-based route search on road networks. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(9):1846-1859.
[23] Xu J J, Gao Y J, Liu C F, Zhao L, Ding Z M. Efficient route search on hierarchical dynamic road networks. Distributed and Parallel Databases, 2015, 33(2):227-252.
[24] Liang S S, Yilmaz E, Shen H, Rijke M D, Croft W B. Search result diversification in short text streams. ACM Transactions on Information Systems, 2017, 36(1):Article No. 8.
[25] Angel A, Koudas N. Efficient diversity-aware search. In Proc. the 30th ACM SIGMOD International Conference on Management of Data, June 2011, pp.781-792.
[26] Khan H A, Sharaf M A. Model-based diversification for sequential exploratory queries. Data Science and Engineering, 2017, 2(2):151-168.
[27] Chen L S, Cong G. Diversity-aware top-k publish/subscribe for text stream. In Proc. the 34th ACM SIGMOD International Conference on Management of Data, May 2015, pp.347-362.
[28] Fan W F, Wang X, Wu Y H. Diversified top-k graph pattern matching. Proceedings of the VLDB Endowment, 2013, 6(13):1510-1521.
[29] Yuan L, Qin l, Lin X M, Chang L J, Zhang W J. Diversified top-k clique search. The International Journal on Very Large Data Bases, 2016, 25(2):171-196.
[30] Carbonell J G, Goldstein-Stewart J. The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Proc. the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, August 1998, pp.335-336.
[31] Vieira M R, Razente H L, Barioni M C, Hadjieleftheriou M, Srivastava D, Traina C, Tsotras V J. On query result diversification. In Proc. the 27th International Conference on Data Engineering, April 2011, pp.1163-1174.
[32] Qin L, Yu Y J, Chang L J. Diversifying top-k results. Proceedings of the VLDB Endowment, 2012, 5(11):1124-1135.
[33] Garey M R, Johnson D S. Computers and intractability:A guide to the theory of NP-completeness. Society for Industrial and Applied Mathematics, 1982, 24(1):90-91.
[34] Jain A, Sarda P, Haritsa J R. Providing diversity in knearest neighbor query results. In Proc. the 8th PacificAsia Conference on Knowledge Discovery and Data Mining, May 2004, pp.404-413.
[35] Lee K C K, Lee W C, Leong H V. Nearest surrounder queries. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(10):1444-1458.
[36] Kucuktunc O, Ferhatosmanoglu H. λ-diverse nearest neighbors browsing for multidimensional data. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(3):481-493.
[37] Ference G, Lee W C, Jung H J, Yang D N. Spatial search for K diverse-near neighbors. In Proc. the 22nd ACM International Conference on Information and Knowledge Management, October 2013, pp.19-28.
[38] Zhang C Y, Zhang Y, Zhang W J, Lin X M, Cheema M A, Wang X Y. Diversified spatial keyword search on road networks. In Proc. the 17th International Conference on Extending Database Technology, March 2014, pp.367-378.
[39] Godsil C, Royle G F. Algebraic Graph Theory. Springer, 2001.
[40] Chiba N, Nishizeki T. Arboricity and subgraph listing algorithms. SIAM Journal on Computing, 1985, 14(1):210-223.
[41] Bao J, Zheng Y, Mokbel M F. Location-based and preference-aware recommendation using sparse geo-social networking data. In Proc. the 20th International Conference on Advances in Geographic Information Systems, November 2012, pp.199-208.
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《计算机科学技术学报》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持：support@magtech.com.cn
总访问量：