We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Meng Chen, Xiaohui Yu, Yang Liu. Mining Object Similarity for Predicting Next Locations[J]. Journal of Computer Science and Technology, 2016, 31(4): 649-660. DOI: 10.1007/s11390-016-1654-2
Citation: Meng Chen, Xiaohui Yu, Yang Liu. Mining Object Similarity for Predicting Next Locations[J]. Journal of Computer Science and Technology, 2016, 31(4): 649-660. DOI: 10.1007/s11390-016-1654-2

Mining Object Similarity for Predicting Next Locations

Funds: 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.
More Information
  • Author Bio:

    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.

  • Corresponding author:

    Yang Liu E-mail: yliu@sdu.edu.cn

  • Received Date: February 25, 2016
  • Revised Date: May 26, 2016
  • Published Date: July 04, 2016
  • 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.

Catalog

    Article views (23) PDF downloads (1243) Cited by()
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return