skip to main content
research-article

Mining significant semantic locations from GPS data

Published:01 September 2010Publication History
Skip Abstract Section

Abstract

With the increasing deployment and use of GPS-enabled devices, massive amounts of GPS data are becoming available. We propose a general framework for the mining of semantically meaningful, significant locations, e.g., shopping malls and restaurants, from such data.

We present techniques capable of extracting semantic locations from GPS data. We capture the relationships between locations and between locations and users with a graph. Significance is then assigned to locations using random walks over the graph that propagates significance among the locations. In doing so, mutual reinforcement between location significance and user authority is exploited for determining significance, as are aspects such as the number of visits to a location, the durations of the visits, and the distances users travel to reach locations. Studies using up to 100 million GPS records from a confined spatio-temporal region demonstrate that the proposal is effective and is capable of outperforming baseline methods and an extension of an existing proposal.

References

  1. M. Ankerst, M. M. Breunig, H.-P. Kriegel, and J. Sander. Optics: Ordering points to identify the clustering structure. In Proc. SIGMOD, pp. 49--60, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  2. D. Ashbrook and T. Starner. Learning significant locations and predicting user movement with GPS. In Proc. ISWC, pp. 101--108, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  3. D. Ashbrook and T. Starner. Using GPS to learn significant locations and predict movement across multiple users. Personal and Ubiquitous Computing, 7(5):275--286, 2003. Google ScholarGoogle ScholarDigital LibraryDigital Library
  4. A. Balmin, V. Hristidis, and Y. Papakonstantinou. Objectrank: Authority-based keyword search in databases. In Proc. VLDB, pp. 564--575, 2004. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. K. Bharat and M. R. Henzinger. Improved algorithms for topic distillation in a hyperlinked environment. In Proc. SIGIR, pp. 104--111, 1998. Google ScholarGoogle ScholarDigital LibraryDigital Library
  6. G. Cong, C. S. Jensen, and D. Wu. Efficient retrieval of the top-k most relevant spatial web objects. PVLDB, 2(1):337--348, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  7. C. H. Q. Ding, X. He, P. Husbands, H. Zha, and H. D. Simon. Pagerank: Hits and a unified framework for link analysis. In Proc. SDM, pp. 249--253, 2003.Google ScholarGoogle ScholarCross RefCross Ref
  8. R. Hariharan and K. Toyama. Project lachesis: parsing and modeling location histories. In Proc. Geographic Information Science, pp. 106--124. 2004.Google ScholarGoogle ScholarCross RefCross Ref
  9. K. Järvelin and J. Kekäläinen. Cumulated gain-based evaluation of IR techniques. ACM TOIS, 20(4):422--446, 2002. Google ScholarGoogle ScholarDigital LibraryDigital Library
  10. J. H. Kang, W. Welbourne, B. Stewart, and G. Borriello. Extracting places from traces of locations. Mobile Computing and Communications Review, 9(3):58--68, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. J. M. Kleinberg. Authoritative sources in a hyperlinked environment. JACM, 46(5):604--632, 1999. Google ScholarGoogle ScholarDigital LibraryDigital Library
  12. A. Langville and C. Meyer. Deeper inside PageRank. Internet Mathematics, 1(3):335--380, 2004.Google ScholarGoogle ScholarCross RefCross Ref
  13. L. Liao, D. J. Patterson, D. Fox, and H. Kautz. Building personal maps from GPS data. Annals of the New York Academy of Sciences, 1093:249--265, 2006.Google ScholarGoogle ScholarCross RefCross Ref
  14. J. Liu, O. Wolfson, and H. Yin. Extracting semantic location from outdoor positioning systems. In Proc. MDM, p. 73, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  15. C. D. Manning, P. Raghavan, and H. Schtze. Introduction to Information Retrieval. Cambridge University Press, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  16. A. Y. Ng, A. X. Zheng, and M. I. Jordan. Stable algorithms for link analysis. In Proc. SIGIR, pp. 258--266, 2001. Google ScholarGoogle ScholarDigital LibraryDigital Library
  17. J. Otterbacher, G. Erkan, and D. R. Radev. Using random walks for question-focused sentence retrieval. In Proc. HLT/EMNLP, pp. 915--922, 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  18. L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. TR 1999--66, Stanford InfoLab, 1999.Google ScholarGoogle Scholar
  19. M.-H. Park, J.-H. Hong, and S.-B. Cho. Location-based recommendation system using Bayesian user's preference model in mobile devices. In Proc. UIC, pp. 1130--1139, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library
  20. F. Schmid and K.-F. Richter. Extracting places from location data streams. In Proc. UbiGIS 2006, 2006.Google ScholarGoogle Scholar
  21. P.-N. Tan, M. Steinbach, and V. Kumar. Introduction to Data Mining. Addison-Wesley Longman Publishing Co., 2005. Google ScholarGoogle ScholarDigital LibraryDigital Library
  22. K. Yatani, K. Tamura, K. Hiroki, M. Sugimoto, and H. Hashizume. Toss-it: Intuitive information transfer techniques for mobile devices using toss and swing actions. IEICE Transactions, 89-D(1):150--157, 2006. Google ScholarGoogle ScholarDigital LibraryDigital Library
  23. Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma. Mining interesting locations and travel sequences from GPS trajectories. In Proc. WWW, pp. 791--800, 2009. Google ScholarGoogle ScholarDigital LibraryDigital Library
  24. C. Zhou, N. Bhatnagar, S. Shekhar, and L. G. Terveen. Mining personally important places from GPS tracks. In Proc. ICDE Workshops, pp. 517--526, 2007. Google ScholarGoogle ScholarDigital LibraryDigital Library

Index Terms

  1. Mining significant semantic locations from GPS data
    Index terms have been assigned to the content through auto-classification.

    Recommendations

    Comments

    Login options

    Check if you have access through your login credentials or your institution to get full access on this article.

    Sign in

    Full Access

    • Published in

      cover image Proceedings of the VLDB Endowment
      Proceedings of the VLDB Endowment  Volume 3, Issue 1-2
      September 2010
      1658 pages

      Publisher

      VLDB Endowment

      Publication History

      • Published: 1 September 2010
      Published in pvldb Volume 3, Issue 1-2

      Qualifiers

      • research-article

    PDF Format

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader