Discovering personal gazetteers: an interactive clustering approach

ABSTRACT

<i>Personal gazetteers</i> record individuals' most important <i>places</i>, such as home, work, grocery store, etc. Using personal gazetteers in location-aware applications offers additional functionality and improves the user experience. However, systems then need some way to acquire them.

This paper explores the use of novel semi-automatic techniques to discover gazetteers from users' travel patterns (time-stamped location data). There has been previous work on this problem, e.g., using ad hoc algorithms [13]or K-Means clustering[4]; however, both approaches have shortcomings. This paper explores a deterministic, density-based clustering algorithm that also uses temporal techniques to reduce the number of uninteresting places that are discovered. We introduce a general framework for evaluating personal gazetteer discovery algorithms and use it to demonstrate the advantages of our algorithm over previous approaches.

REFERENCES

• 1: AccuTracking Web Site. http://www.accutracking.com.
• 2: Open GIS Consortium, Inc. (OGC). http://www.opengis.org.
• 3: University of Minnesota MapServer. http://www.mapserver.umn.edu.
• 4: D. Ashbrook, Learning Significant Locations and Predicting User Movement with GPS, Proceedings of the 6th IEEE International Symposium on Wearable Computers, p.101, October 07-10, 2002
• 5: J. Burrell and G. Gay. E-graffiti: evaluating real-world use of a context-aware system. Interacting with Computers, 2001.
• 6: Fredrik Espinoza , Per Persson , Anna Sandin , Hanna Nyström , Elenor Cacciatore , Markus Bylund, GeoNotes: Social and Navigational Aspects of Location-Based Information Systems, Proceedings of the 3rd international conference on Ubiquitous Computing, p.2-17, September 30-October 02, 2001, Atlanta, Georgia, USA
• 7: M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining, 1996.
• 8: Franck, Karen A., and L. H. Schneekloth, editors. Ordering space: types in architecture and design. Van Nostrand Reinhold, 1994.
• 9: R. Genereux, L. Ward, and J. Russell. The behavioral component in the meaning of places. Journal of Environmental Psychology, 3:43--55, 1983.
• 10: W. Griswold, G. Shanahan, S. Brown, R. Boyer, M. Ratto, R. Shapiro, and T. Truong. Activecampus - experiments in community-oriented ubiquitous computing. Technical report, UC San Diego, 2003.
• 11: Quentin Jones , Sukeshini A. Grandhi , Steve Whittaker , Keerti Chivakula , Loren Terveen, Putting systems into place: a qualitative study of design requirements for location-aware community systems, Proceedings of the 2004 ACM conference on Computer supported cooperative work, November 06-10, 2004, Chicago, Illinois, USA [doi>10.1145/1031607.1031640]
• 12: B. Kramer. Classification of generic places: Explorations with implications for evaluation. Journal of Environmental Psychology, 15:3--22, 1995.
• 13: Natalia Marmasse , Chris Schmandt, Location-Aware Information Delivery with ComMotion, Proceedings of the 2nd international symposium on Handheld and Ubiquitous Computing, p.157-171, September 25-27, 2000, Bristol, UK
• 14: Jörg Sander , Martin Ester , Hans-Peter Kriegel , Xiaowei Xu, Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications, Data Mining and Knowledge Discovery, v.2 n.2, p.169-194, June 1998 [doi>10.1023/A:1009745219419]
• 15: Loren Terveen , David W. McDonald, Social matching: A framework and research agenda, ACM Transactions on Computer-Human Interaction (TOCHI), v.12 n.3, p.401-434, September 2005 [doi>10.1145/1096737.1096740]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms, Human Factors

Keywords:
GPS, location-aware, personal gazetteer, personal places, spatio-temporal clustering