.tabbox {width:400px; margin-top: 15px;margin-bottom: 5px} .tabmenu {width:400px;height:28px;border-left:1px solid #CCC;border-top:1px solid #ccc;} .tabmenu ul {margin:0;padding:0;list-style-type: none;} .tabmenu li { text-align:center; float:left; display:block; width:99px; overflow:hidden; background-color: #f1f1f1; line-height:27px; border-right:#ccc 1px solid; border-bottom:#ccc 1px solid; display:inline;} .tabmenu .cli {text-align:center;float:left;display:block;width:99px;overflow:hidden;background-color: #fff;line-height:27px;border-right:#ccc 1px solid;border-bottom:#fff 1px solid;display:inline; cursor:pointer; color: #810505; font-weight:bold} #tabcontent {width:399px;background-color:#fff;border-left:#CCC 1px solid;border-right:#CCC 1px solid;border-bottom:#CCC 1px solid; height:60px;} #tabcontent ul {margin:0;padding:5px;list-style-type: none;} #tabcontent .hidden {display:none;} Search Browse by Issue Fig/Tab Adv Search
 HOME ABOUT JCST AUTHORS REVIEWERS PUBLISHED PAPERS FORTHCOMING PAPERS

›› 2016, Vol. 31 ›› Issue (4): 649-660.

Special Issue: Data Management and Data Mining

• Special Section on Data Management and Data Mining 2016 •

### Mining Object Similarity for Predicting Next Locations

Meng Chen1(陈勐), Xiaohui Yu1,2(禹晓辉), Member, CCF, IEEE, and Yang Liu1,*(刘洋), Member, CCF, IEEE

1. 1 School of Computer Science and Technology, Shandong University, Jinan 250101, China;
2 School of Information Technology, York University, Toronto, M3 J1 P3, Canada
• Received:2016-02-26 Revised:2016-05-27 Online:2016-07-05 Published:2016-07-05
• Contact: Yang Liu E-mail:yliu@sdu.edu.cn
• About author:Meng Chen received his B.S. degree in software engineering in 2011 from Shandong University, Jinan. He is currently a Ph.D. candidate in the School of Computer Science and Technology, Shandong University, Jinan. His research interest is in the area of data mining.
• Supported by:

This work was supported in part by the National Basic Research 973 Program of China under Grant No. 2015CB352502, the National Natural Science Foundation of China under Grant Nos. 61272092 and 61572289, the Natural Science Foundation of Shandong Province of China under Grant Nos. ZR2012FZ004 and ZR2015FM002, the Science and Technology Development Program of Shandong Province of China under Grant No. 2014GGE27178, and the NSERC (Natural Sciences and Engineering Research Council of Canada) Discovery Grants.

Next location prediction is of great importance for many location-based applications. With the virtue of solid theoretical foundations, Markov-based approaches have gained success along this direction. In this paper, we seek to enhance the prediction performance by understanding the similarity between objects. In particular, we propose a novel method, called weighted Markov model (weighted-MM), which exploits both the sequence of just-passed locations and the object similarity in mining the mobility patterns. To this end, we first train a Markov model for each object with its own trajectory records, and then quantify the similarities between different objects from two aspects:spatial locality similarity and trajectory similarity. Finally, we incorporate the object similarity into the Markov model by considering the similarity as the weight of the probability of reaching each possible next location, and return the top-rankings as results. We have conducted extensive experiments on a real dataset, and the results demonstrate significant improvements in prediction accuracy over existing solutions.

 [1] Chen W, Zhao L, Xu J J, Liu G F, Zheng K, Zhou X. Trip oriented search on activity trajectory. Journal of Computer Science and Technology, 2015, 30(4):745-761.[2] Park H, Lee Y J, Chae J, Choi W. Online approach for spatio-temporal trajectory data reduction for portable devices. Journal of Computer Science and Technology, 2013, 28(4):597-604.[3] Hsieh H P, Lin S D, Zheng Y. Inferring air quality for station location recommendation based on urban big data. In Proc. the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2015, pp.437-446.[4] Gao H J, Tang J L, Hu X, Liu H. Content-aware point of interest recommendation on location-based social networks. In Proc. the 29th AAAI Conference on Artificial Intelligence, January 2015, pp.1721-1727.[5] Xue G, Li Z, Zhu H, Liu Y. Traffic-known urban vehicular route prediction based on partial mobility patterns. In Proc. International Conference on Parallel and Distributed Systems, December 2009, pp.369-375.[6] Chen M, Liu Y, Yu X. NLPMM:A next location predictor with Markov modeling. In Proc. the 18th Pacific-Asia Conference on Knowledge Discovery and Data Mining, May 2014, pp.186-197.[7] Chen M, Yu X, Liu Y. Mining moving patterns for predicting next location. Information Systems, 2015, 54:156-168.[8] Simmons R, Browning B, Zhang Y, Sadekar V. Learning to predict driver route and destination intent. In Proc. International Conference on Intelligent Transportation Systems, September 2006, pp.127-132.[9] Liao L, Patterson D J, Fox D, Kautz H. Learning and inferring transportation routines. Artificial Intelligence, 2007, 171(5/6):311-331.[10] Monreale A, Pinelli F, Trasarti R, Giannotti F. WhereNext:A location predictor on trajectory pattern mining. In Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, June 28-July 1, 2009, pp.637-646.[11] Morzy M. Mining frequent trajectories of moving objects for location prediction. In Proc. International Conference on Machine Learning and Data Mining, July 2007, pp.667-680.[12] Xue A Y, Zhang R, Zheng Y, Xie X, Huang J, Xu Z. Destination prediction by subtrajectory synthesis and privacy protection against such prediction. In Proc. IEEE International Conference on Data Engineering, April 2013, pp.254-265.[13] Zhou J, Tung A K, Wu W, Ng W S. A "semi-lazy" approach to probabilistic path prediction in dynamic environments. In Proc. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2013, pp.748-756.[14] Ye J, Zhu Z, Cheng H. What's your next move:User activity prediction in location-based social networks. In Proc. SIAM International Conference on Data Mining, May 2013, pp.171-179.[15] Pan B, Demiryurek U, Shahabi C. Utilizing real-world transportation data for accurate traffic prediction. In Proc. the 12th IEEE International Conference on Data Mining, December 2012, pp.595-604.[16] Zhang D, Zhao S, Yang L T, Chen M, Wang Y, Liu H. NextMe:Localization using cellular traces in Internet of things. IEEE Transactions on Industrial Informatics, 2015, 11(2):302-312.[17] Ye M, Yin P, Lee W C, Lee D L. Exploiting geographical influence for collaborative point-of-interest recommendation. In Proc. International Conference on Research on Development in Information Retrieval, July 2011, pp.325-334.[18] Yuan Q, Cong G, Ma Z, Sun A, Magnenat-Thalmann N. Time-aware point-of-interest recommendation. In Proc. the 36th International Conference on Research on Development in Information Retrieval, July 2013, pp.363-372.[19] Vlachos M, Kollios G, Gunopulos D. Discovering similar multidimensional trajectories. In Proc. the 18th IEEE International Conference on Data Engineering, February 26-March 1, 2002, pp.673-684.[20] Keogh E. Exact indexing of dynamic time warping. In Proc. the 28th International Conference on Very Large Data Bases, August 2002, pp.406-417.[21] Chen L, Özsu M T, Oria V. Robust and fast similarity search for moving object trajectories. In Proc. International Conference on Management of Data, June 2005, pp.491-502.[22] Ying J C, Lu H C, Lee W C, Weng T C, Tseng V S. Mining user similarity from semantic trajectories. In Proc. ACM SIGSPATIAL International Workshop on Location Based Social Networks, November 2010, pp.19-26.[23] Velpula V B, Prasad M K. TCMVS:A novel trajectory clustering technique based on multi-view similarity. Cybernetics Information Technologies, 2015, 15(2):53-62.[24] Wu Q, Ng M K, Ye Y. Cotransfer learning using coupled Markov chains with restart. IEEE Intelligent Systems, 2013, 29(4):26-33.[25] Miller F P, Vandome A F, McBrewster J (eds.). Additive Smoothing. Alphascript Publishing, 2010.[26] Ertoz L, Steinbach M, Kumar V. A new shared nearest neighbor clustering algorithm and its applications. In Proc. the Workshop on Clustering High Dimensional Data and Its Applications at the 2nd SIAM International Conference on Data Mining, April 2002, pp.105-115.[27] Chen M, Liu Y, Yu X. Predicting next locations with object clustering and trajectory clustering. In Proc. the 19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, May 2015, pp.344-356.
 No related articles found!
Viewed
Full text

Abstract

Cited

Shared
Discussed
 [1] Lu Qi; Zhang Fubo; Qian Jiahua;. Program Slicing:Its Improved Algorithm and Application in Verification[J]. , 1988, 3(1): 29 -39 . [2] Xu Jie; Li Qingnan; Huang Shize; Xu Jiangfeng;. DFTSNA:A Distributed Fault-Tolerant Shipboard System[J]. , 1990, 5(2): 109 -116 . [3] Jia Li, Li-Yong Shen, and Xiao-Shan Gao. Proper Reparametrization of Rational Ruled Surface[J]. , 2008, 23(2): 290 -297 . [4] Gang Huang and Lian-Shan Sun. An Access Control Framework for Reflective Middleware[J]. , 2008, 23(6 ): 895 -904 . [5] Shao-Liang Peng, Member, CCF, ACM, IEEE, Shan-Shan Li, Xiang-Ke Liao, Yu-Xing Peng, and Nong Xiao, Member, CCF, ACM, IEEE. Estimation of a Population Size in Large-Scale Wireless Sensor Networks[J]. , 2009, 24(5): 987 -inside back cover . [6] Antonio Fernández Anta, Senior Member, ACM, IEEE, Ernesto Jiménez and Michel Raynal. Eventual Leader Election with Weak Assumptions on Initial Knowledge, Communication Reliability, and Synchrony[J]. , 2010, 25(6): 1267 -1281 . [7] Yuan Li, Xing-Chen Wang, Lin Huang, Yun-Lei Zhao. Order-Revealing Encryption: File-Injection Attack and Forward Security[J]. Journal of Computer Science and Technology, 2021, 36(4): 877 -895 . [8] Fan Zhang, Xin Zhang, Xue-Ying Qin, Cai-Ming Zhang. Enlarging Image by Constrained Least Square Approach with Shape Preserving[J]. , 2015, 30(3): 489 -498 . [9] Peng-Peng Chen, Hai-Long Sun, Yi-Li Fang, Jin-Peng Huai. Collusion-Proof Result Inference in Crowdsourcing[J]. , 2018, 33(2): 351 -365 . [10] Wen-Guang Chen, Xue-Ming Si. Preface[J]. , 2018, 33(3): 531 -532 .
 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