Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (4): 818-838.doi: 10.1007/s11390-019-1944-6

Special Issue: Data Management and Data Mining

• Data Management and Data Mining • Previous Articles     Next Articles

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

Supplement

1

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!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

 Home
Editorial Board
Author Guidelines
Subscription		 Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved