Mining interesting locations and travel sequences from GPS trajectories

ABSTRACT

The increasing availability of GPS-enabled devices is changing the way people interact with the Web, and brings us a large amount of GPS trajectories representing people's location histories. In this paper, based on multiple users' GPS trajectories, we aim to mine interesting locations and classical travel sequences in a given geospatial region. Here, interesting locations mean the culturally important places, such as Tiananmen Square in Beijing, and frequented public areas, like shopping malls and restaurants, etc. Such information can help users understand surrounding locations, and would enable travel recommendation. In this work, we first model multiple individuals' location histories with a tree-based hierarchical graph (TBHG). Second, based on the TBHG, we propose a HITS (Hypertext Induced Topic Search)-based inference model, which regards an individual's access on a location as a directed link from the user to that location. This model infers the interest of a location by taking into account the following three factors. 1) The interest of a location depends on not only the number of users visiting this location but also these users' travel experiences. 2) Users' travel experiences and location interests have a mutual reinforcement relationship. 3) The interest of a location and the travel experience of a user are relative values and are region-related. Third, we mine the classical travel sequences among locations considering the interests of these locations and users' travel experiences. We evaluated our system using a large GPS dataset collected by 107 users over a period of one year in the real world. As a result, our HITS-based inference model outperformed baseline approaches like rank-by-count and rank-by-frequency. Meanwhile, when considering the users' travel experiences and location interests, we achieved a better performance beyond baselines, such as rank-by-count and rank-by-interest, etc.

REFERENCES

• 1: Bikely: http://www.bikely.com/
• 2: GPS Track route exchange forum: http://www.gpsxchange.com/
• 3: GPS sharing: http://gpssharing.com/.
• 4: Gregory D. Abowd , Christopher G. Atkeson , Jason Hong , Sue Long , Rob Kooper , Mike Pinkerton, Cyberguide: a mobile context-aware tour guide, Wireless Networks, v.3 n.5, p.421-433, Oct. 1997 [doi>10.1023/A:1019194325861]
• 5: Daniel Ashbrook , Thad Starner, Using GPS to learn significant locations and predict movement across multiple users, Personal and Ubiquitous Computing, v.7 n.5, p.275-286, October 2003 [doi>10.1007/s00779-003-0240-0]
• 6: Ashweeni Beeharee , Anthony Steed, Exploiting real world knowledge in ubiquitous applications, Personal and Ubiquitous Computing, v.11 n.6, p.429-437, August 2007 [doi>10.1007/s00779-006-0091-6]
• 7: Nathan Eagle , Alex (Sandy) Pentland, Reality mining: sensing complex social systems, Personal and Ubiquitous Computing, v.10 n.4, p.255-268, March 2006 [doi>10.1007/s00779-005-0046-3]
• 8: Fosca Giannotti , Mirco Nanni , Fabio Pinelli , Dino Pedreschi, Trajectory pattern mining, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281230]
• 9: Hariharan, R. et al. Project Lachesis: Parsing and Modeling Location Histories, In Proceedings of GIScience, (Park Utah, October 2004), ACM Press: 106--124.
• 10: Tzvetan Horozov , Nitya Narasimhan , Venu Vasudevan, Using Location for Personalized POI Recommendations in Mobile Environments, Proceedings of the International Symposium on Applications on Internet, p.124-129, January 23-27, 2006 [doi>10.1109/SAINT.2006.55]
• 11: Krumm, J.et al. Predestination: Inferring Destinations from Partial Trajectories. In Proceedings of the Ubicomp'03, (Orange County USA, September 2003). Springer Press: 243--260.
• 12: Quannan Li , Yu Zheng , Xing Xie , Yukun Chen , Wenyu Liu , Wei-Ying Ma, Mining user similarity based on location history, Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems, November 05-07, 2008, Irvine, California [doi>10.1145/1463434.1463477]
• 13: Liao, L., et al. Building Personal Maps from GPS Data. In proceedings of IJCAI MOO05, Springer Press(2005): 249--265
• 14: Park, M., H. Location-Based Recommendation System Using Bayesian User's Preference Model in Mobile Devices. In Proc. UIC'07 (Hong Kong, China, July 2007). Springer Press:1130--1139
• 15: Patterson, D., J. et al. Inferring High--Level Behavior from Low-Level Sensors. In Proc. of Ubicomp'03, Springer Press (2003), 73--89
• 16: Nikos Mamoulis , Huiping Cao , George Kollios , Marios Hadjieleftheriou , Yufei Tao , David W. Cheung, Mining, indexing, and querying historical spatiotemporal data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014080]
• 17: Rainer Simon , Peter Fröhlich, A mobile application framework for the geospatial web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242624]
• 18: Takeuchi, Y. et al. CityVoyager: An Outdoor Recommendation System Based on User Location History. In Proceedings of UIC'2006, (Berlin, 2006), Springer Press: 625--636.
• 19: Yu Zheng , Like Liu , Longhao Wang , Xing Xie, Learning transportation mode from raw gps data for geographic applications on the web, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367532]
• 20: Yu Zheng , Longhao Wang , Ruochi Zhang , Xing Xie , Wei-Ying Ma, GeoLife: Managing and Understanding Your Past Life over Maps, Proceedings of the The Ninth International Conference on Mobile Data Management, p.211-212, April 27-30, 2008 [doi>10.1109/MDM.2008.20]
• 21: Yu Zheng , Quannan Li , Yukun Chen , Xing Xie , Wei-Ying Ma, Understanding mobility based on GPS data, Proceedings of the 10th international conference on Ubiquitous computing, September 21-24, 2008, Seoul, Korea [doi>10.1145/1409635.1409677]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering; Retrieval models
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
GPS trajectories, location recommendation, spatial data mining, user travel experience