Xin Cao
Christian S. Jensen
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.
- 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 Scholar
Digital Library
- D. Ashbrook and T. Starner. Learning significant locations and predicting user movement with GPS. In Proc. ISWC, pp. 101--108, 2002. Google ScholarDigital Library
- 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 ScholarDigital Library
- A. Balmin, V. Hristidis, and Y. Papakonstantinou. Objectrank: Authority-based keyword search in databases. In Proc. VLDB, pp. 564--575, 2004. Google ScholarDigital Library
- K. Bharat and M. R. Henzinger. Improved algorithms for topic distillation in a hyperlinked environment. In Proc. SIGIR, pp. 104--111, 1998. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarCross Ref
- R. Hariharan and K. Toyama. Project lachesis: parsing and modeling location histories. In Proc. Geographic Information Science, pp. 106--124. 2004.Google ScholarCross Ref
- K. Järvelin and J. Kekäläinen. Cumulated gain-based evaluation of IR techniques. ACM TOIS, 20(4):422--446, 2002. Google ScholarDigital Library
- 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 ScholarDigital Library
- J. M. Kleinberg. Authoritative sources in a hyperlinked environment. JACM, 46(5):604--632, 1999. Google ScholarDigital Library
- A. Langville and C. Meyer. Deeper inside PageRank. Internet Mathematics, 1(3):335--380, 2004.Google ScholarCross Ref
- 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 ScholarCross Ref
- J. Liu, O. Wolfson, and H. Yin. Extracting semantic location from outdoor positioning systems. In Proc. MDM, p. 73, 2006. Google ScholarDigital Library
- C. D. Manning, P. Raghavan, and H. Schtze. Introduction to Information Retrieval. Cambridge University Press, 2008. Google ScholarDigital Library
- A. Y. Ng, A. X. Zheng, and M. I. Jordan. Stable algorithms for link analysis. In Proc. SIGIR, pp. 258--266, 2001. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 Scholar
- 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 ScholarDigital Library
- F. Schmid and K.-F. Richter. Extracting places from location data streams. In Proc. UbiGIS 2006, 2006.Google Scholar
- P.-N. Tan, M. Steinbach, and V. Kumar. Introduction to Data Mining. Addison-Wesley Longman Publishing Co., 2005. Google ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
- 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 ScholarDigital Library
Index Terms
- Mining significant semantic locations from GPS data
Recommendations
Mining interesting locations and travel sequences from GPS trajectories
WWW '09: Proceedings of the 18th international conference on World wide webThe 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 ...
Mining GPS data to determine interesting locations
IIWeb '11: Proceedings of the 8th International Workshop on Information Integration on the Web: in conjunction with WWW 2011It is possible to obtain fine grained location information fairly easily using Global Positioning System (GPS) enabled devices. It becomes easy to track an individual's location and trace her trajectory using such devices. By aggregating this data and ...
Algorithm for detecting significant locations from raw GPS data
DS'10: Proceedings of the 13th international conference on Discovery scienceWe present a fast algorithm for probabilistically extracting significant locations from raw GPS data based on data point density. Extracting significant locations from raw GPS data is the first essential step of algorithms designed for location-aware ...
Comments