Mining user similarity based on location history

ABSTRACT

The pervasiveness of location-acquisition technologies (GPS, GSM networks, etc.) enable people to conveniently log the location histories they visited with spatio-temporal data. The increasing availability of large amounts of spatio-temporal data pertaining to an individual's trajectories has given rise to a variety of geographic information systems, and also brings us opportunities and challenges to automatically discover valuable knowledge from these trajectories. In this paper, we move towards this direction and aim to geographically mine the similarity between users based on their location histories. Such user similarity is significant to individuals, communities and businesses by helping them effectively retrieve the information with high relevance. A framework, referred to as hierarchical-graph-based similarity measurement (HGSM), is proposed for geographic information systems to consistently model each individual's location history and effectively measure the similarity among users. In this framework, we take into account both the sequence property of people's movement behaviors and the hierarchy property of geographic spaces. We evaluate this framework using the GPS data collected by 65 volunteers over a period of 6 months in the real world. As a result, HGSM outperforms related similarity measures, such as the cosine similarity and Pearson similarity measures.

REFERENCES

• 1: Bikely: http://www.bikely.com/
• 2: GPS Track route exchange forum: http://www.gpsxchange.com/
• 3: GPS sharing: http://gpssharing.com/
• 4: Gediminas Adomavicius , Alexander Tuzhilin, Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Art and Possible Extensions, IEEE Transactions on Knowledge and Data Engineering, v.17 n.6, p.734-749, June 2005 [doi>10.1109/TKDE.2005.99]
• 5: Brunato, M., Battiti, R., Villani, A., Delai, A. A Location-Dependent Recommender System for the Web. In Proc. of the MobEA Workshop, 2002.
• 6: 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]
• 7: 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]
• 8: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 9: John Krumm , Eric Horvitz, Predestination: Where Do You Want to Go Today?, Computer, v.40 n.4, p.105-107, April 2007 [doi>10.1109/MC.2007.141]
• 10: Krumm, J., Horvitz, Eric. Predestination: Inferring Destinations from Partial Trajectories. In Proc. of UBICOMP'06, Springer-Verlag Press(2003), 243--260
• 11: Krumm, J., Horvitz, Eric. LOCADIO: Inferring Motion and Location from Wi-Fi Signal Strengths. In Proc. of Mobiquitous 2004, IEEE Press (2004), 4--13.
• 12: Liao, Ll, Patterson, D. J., Fox, D., Kautz, H. Building Personal Maps from GPS Data. In proc. of IJCAI MOO05, Springer Press(2005), 249--265
• 13: Liao, L., Fox, D., Kautz, H. Learning and Inferring Transportation Routines. In Proc. of the National Conference on Artificial Intelligence. ACM Press (2004), 348--353.
• 14: Greg Linden , Brent Smith , Jeremy York, Amazon.com Recommendations: Item-to-Item Collaborative Filtering, IEEE Internet Computing, v.7 n.1, p.76-80, January 2003 [doi>10.1109/MIC.2003.1167344]
• 15: Patterson, D. J., Liao, L., Fox, D., Kautz, H. Inferring High-Level Behavior from Low-Level Sensors. In Proc. of UBICOMP'03, Springer Press (2003), 73--89
• 16: Sohn, T., Varshavsky, A., LaMarca, A., Chen, Y. M. Mobility Detection Using Everyday GSM Traces. In Proc. of UBICOMP'06, Springer-Verlag Press(2006), 212--224
• 17: Ellen Spertus , Mehran Sahami , Orkut Buyukkokten, Evaluating similarity measures: a large-scale study in the orkut social network, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081956]
• 18: Sarwar, B., Karypis, G., Konstan, J., and Riedl, J. Application of Dimensionality Reduction Recommender System -- A Case Study, In ACM WebKDD Workshop, 2000.
• 19: Takeuchi, Y. Sugimoto, M. CityVoyager: An Outdoor Recommendation System Based on User Location History. In Proc. Ubicomp'2006, Springer Berlin (2006), 625--636
• 20: Wan-Shiou Yang , Hung-Chi Cheng , Jia-Ben Dia, A location-aware recommender system for mobile shopping environments, Expert Systems with Applications: An International Journal, v.34 n.1, p.437-445, January, 2008 [doi>10.1016/j.eswa.2006.09.033]
• 21: 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]

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
GPS logs, similar sequence matching, spatio-temporal data mining, user similarity