Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Context Trees: Augmenting Geospatial Trajectories with Context

Published: 10 October 2016 Publication History

Abstract

Exposing latent knowledge in geospatial trajectories has the potential to provide a better understanding of the movements of individuals and groups. Motivated by such a desire, this work presents the context tree, a new hierarchical data structure that summarises the context behind user actions in a single model. We propose a method for context tree construction that augments geospatial trajectories with land usage data to identify such contexts. Through evaluation of the construction method and analysis of the properties of generated context trees, we demonstrate the foundation for understanding and modelling behaviour afforded. Summarising user contexts into a single data structure gives easy access to information that would otherwise remain latent, providing the basis for better understanding and predicting the actions and behaviours of individuals and groups. Finally, we also present a method for pruning context trees for use in applications where it is desirable to reduce the size of the tree while retaining useful information.

References

[1]
Saif Ahmad, Tugba Taskaya-Temizel, and Khurshid Ahmad. 2004. Summarizing time series: Learning Patterns in ‘volatile’ series. In Proceedings of the 5th International Conference on Intelligent Data Engineering and Automated Learning. Springer, Exeter, 523--532. 10.1007/978-3-540-28651-6_77
[2]
Juan Antonio Alvarez-Garcia, Juan Antonio Ortega, Luis Gonzalez-Abril, and Francisco Velasco. 2010. Trip destination prediction based on past GPS log using a hidden markov model. Expert Syst. Applic. 37, 12 (2010), 8166--8171.
[3]
Christos Anagnostopoulos, Athanasios Tsounis, and Stathes Hadjiefthymiades. 2006. Context awareness in mobile computing environments. Wireless Pers. Commun. 42, 3 (2006), 445--464. 10.1007/s11277-006-9187-6
[4]
Gennady Andrienko, Natalia Andrienko, Christophe Hurter, Salvatore Rinzivillo, and Stefan Wrobel. 2011. From movement tracks through events to places: Extracting and characterizing significant places from mobility data. In Proceedings of the IEEE Conference on Visual Analytics Science and Technology. 161--170.
[5]
Daniel Ashbrook and Thad Starner. 2002. Learning significant locations and predicting user movement with GPS. In Proceedings of the 6th International Symposium on Wearable Computers. 101--108.
[6]
Daniel Ashbrook and Thad Starner. 2003. Using GPS to learn significant locations and predict movement across multiple users. Pers. Ubiq. Comput. 7, 5 (2003), 275--286. 1007/s00779-003-0240-0
[7]
Athanasios Bamis and Andreas Savvides. 2011. Exploiting human state information to improve GPS sampling. In Proceedings of the IEEE International Conference on Pervasive Computing and Communications Workshops. 32--37.
[8]
Jie Bao, Yu Zheng, David Wilkie, and Mohamed Mokbel. 2015. Recommendations in location-based social networks: A survey. GeoInformatica 19, 3 (2015), 525--565.
[9]
Tengfei Bao, Huanhuan Cao, Enhong Chen, Jilei Tian, and Hui Xiong. 2011. An unsupervised approach to modelling personalized contexts of mobile users. Knowl. Inform. Syst. 31, 2 (2011), 345--370. 10.1007/s10115-011-0417-1
[10]
Huanhuan Cao, Tengfei Bao, Qiang Yang, Enhong Chen, and Jilei Tian. 2010. An effective approach for mining mobile user habits. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 1677--1680.
[11]
Huiping Cao, Nikos Mamoulis, and David Cheung. 2005. Mining frequent spatio-temporal sequential patterns. In Proceedings of the 5th IEEE International Conference on Data Mining. 82--89.
[12]
Huiping Cao, Nikos Mamoulis, and David W. Cheung. 2007. Discovery of periodic patterns in spatiotemporal sequences. IEEE Trans. Knowl. Data Eng. 19, 4 (2007), 453--467. 1109/TKDE.2007.1002
[13]
Qing Cao, Bouchra Bouqata, Patricia D. Mackenzie, Daniel Messier, and Josheph J. Salvo. 2009. A grid-based clustering method for mining frequent trips from large-scale, event-based telematics datasets. In Proceedings of the 2009 IEEE International Conference on Systems, Man and Cybernetics. 2996--3001.
[14]
Chao Chen, Daqing Zhang, Pablo Samuel Castro, Nan Li, Lin Sun, and Shijian Li. 2011. Real-time detection of anomalous taxi trajectories from GPS traces. In Proceedings of the 8th International ICST Conference on Mobile and Ubiquitous Systems. 63--74.
[15]
Ling Chen, Mingqi Lv, and Gencai Chen. 2010. A system for destination and future route prediction based on trajectory mining. Perv. Mobile Comput. 6, 6 (2010), 657--676. 10.1016/j.pmcj.2010.08.004
[16]
Peng Chen, Zhao Lu, and Junzhong Gu. 2009. Vehicle travel time prediction algorithm based on historical data and shared location. In Proceedings of the 5th International Joint Conference on INC, IMS and IDC. 1632--1637.
[17]
Yohan Chon, Elmurod Talipov, Hyojeong Shin, and Hojung Cha. 2011. Mobility prediction-based smartphone energy optimization for everyday location monitoring. In Proceedings of the 17th International Conference on World Wide Web. 82--85.
[18]
Tanzeem Choudhury, Sunny Consolvo, Beverly Harrison, Jeffrey Hightower, Louis LeGrand, Ali Rahimi, Adam Rea, Gaetano Borriello, Bruce Hemingway, Predrag Klasnja, Karl Koscher, James A. Landay, Jonathan Lester, Danny Wyatt, and Dirk Haehnel. 2008. The mobile sensing platform: An embedded activity recognition system. Perv. Comput. 7, 2 (2008), 32--41.
[19]
Anind Dey and Gregory Abowd. 1999. Towards a better understanding of context and context-awareness. In Proceedings of the 1st International Symposium on Handheld and Ubiquitous Computing. Karlsruhe, 304--307.
[20]
Nathan Eagle and Alex Sandy Pentland. 2009. Eigenbehaviors: Identifying structure in routine. Behav. Ecol. Sociobiol. 63, 7 (2009), 1057--1066.
[21]
Nathan Eagle and Alex Sandy Pentland. 2005. Reality mining: Sensing complex social systems. Pers. Ubiq. Comput. 10, 4 (2005), 255--268.
[22]
Mica R. Endsley. 1995. Toward a theory of situation awareness in dynamic systems. Hum. Factors: J. Hum. Factors Ergon. Soc. 37 (1995), 32--64. Issue 1.
[23]
Mica R. Endsley. 2000. Theoretical underpinnings of situation awareness: A critical review. In Situation Awareness Analysis and Measurement, Mica R. Endsley and Daniel J. Garland (Eds.). Routledge, 3--32.
[24]
Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 16th International Conference on Knowledge Discovery and Data Mining. 226--231.
[25]
Katayoun Farrahi and Daniel Gatica-Perez. 2008. Daily routine classification from mobile phone data. In Proceedings of the 5th International Workshop on Machine Learning for Multimodal Interaction. 173--184.
[26]
Katayoun Farrahi and Daniel Gatica-Perez. 2010. Probabilistic mining of socio-geographic routines from mobile phone data. IEEE J. Select. Top. Sign. Process. 4, 4 (2010), 746--755. 10.1109/JSTSP.2010.2049513
[27]
Jun Fukano, Tomohiro Mashita, Takahiro Hara, and Kiyoshi Kiyokawa. 2013. A next location prediction method for smartphones using blockmodels. In Proceedings of the IEEE Conference on Virtual Reality. 1--4.
[28]
Huiji Gao, Jiliang Tang, and Huan Liu. 2012. Mobile location prediction in spatio-temporal context. In Proceedings of the Nokia Mobile Data Challenge (MDC) Workshop in Conjunction with Pervasive.
[29]
Fosca Giannotti, Mirco Nanni, Fabio Pinelli, and Dino Pedreschi. 2007. Trajectory pattern mining. In Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 330--339.
[30]
Joachim Gudmundsson, Marc van Kreveld, and Bettina Speckmann. 2004. Efficient detection of motion patterns in spatio-temporal data sets. In Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems. 250--257.
[31]
Riccardo Guidotti, Roberto Trasarti, and Mirco Nanni. 2015. TOSCA: TwO-steps clustering algorithm for personal locations detection. In Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.
[32]
Newton Howard. 2002. Theory of Intention Awareness in Tactical Military Intelligence: Reducing Uncertainty by Understanding the Cognitive Architecture of Intentions. AuthorHouse, Bloomington.
[33]
Newton Howard and Erik Cambria. 2013. Intention awareness: Improving upon situation awareness in human-centric environments. Human-cent. Comput. Inform. Sci. 3, 1 (2013), 17. 10.1186/2192-1962-3-9
[34]
Baoxing Huai, Enhong Chen, Hengshu Zhu, Hui Xiong, Tengfei Bao, Qi Liu, and Jilei Tian. 2014. Toward personalized context recognition for mobile users: A semisupervised bayesian HMM approach. ACM Trans. Knowl. Discov. Data 9, 2 (2014), 10:1--10:29.
[35]
Eunju Kim, Sumi Helal, and Diane Cook. 2010. Human activity recognition and pattern discovery. Perv. Comput. 9, 1 (2010), 48--53.
[36]
Niko Kiukkonen, Jan Blom, Olivier Dousse, Daniel Gatica-Perez, and Juha Laurila. 2010. Towards rich mobile phone datasets: Lausanne data collection campaign. In Proceedings of the First Workshop on Modeling and Retrieval of Context. Berlin.
[37]
John Krumm and Eric Horvitz. 2006. Predestination: Inferring destinations from partial trajectories. In Proceedings of the 13th International Conference on Ubiquitous Computing. 243--260.
[38]
John Krumm and Dany Rouhana. 2013. Placer: Semantic place labels from diary data. In Proceedings of the ACM International Joint Conference on Pervasive and Ubiquitous Computing. 163--172.
[39]
Juha K. Laurila, Daniel Gatica-Perez, Imad Aad, Jan Blom, Olivier Bornet, Trinh Minh Tri Do, Olivier Dousse, Julien Eberle, and Markus Miettinen. 2012. The mobile data challenge: Big data for mobile computing research. In Proceedings of the Nokia Mobile Data Challenge (MDC) Workshop in Conjunction with Pervasive.
[40]
Rikard Laxhammar and Goran Falkman. 2011. Sequential conformal anomaly detection in trajectories based on hausdorff distance. In Proceedings of the 14th International Conference on Information Fusion. 1--8.
[41]
Rikard Laxhammar and Goran Falkman. 2014. Online learning and sequential anomaly detection in trajectories. IEEE Trans. Pattern Anal. Mach. Intell. 36, 6 (2014), 1158--1173. 10.1109/TPAMI.2013.172
[42]
Seon-Woo Lee and Kenji Mase. 2002. Activity and location recognition using wearable sensors. Perv. Comput. 1, 3 (2002), 24--32.
[43]
Tayeb Lemlouma and Nabil Layaida. 2004. Context-aware adaptation for mobile devices. In Proceedings of the IEEE International Conference on Mobile Data Management. 106--111. 10.1109/MDM.2004.1263048
[44]
Jonathan Lester, Tanzeem Choudhury, Nicky Kern, Gaetano Borriello, and Blake Hannaford. 2005. A hybrid discriminative/generative approach for modeling human activities. In Proceedings of the 19th International Joint Conference on Artificial Intelligence. 766--772.
[45]
Zhenhui Li, Bolin Ding, Jiawei Han, Roland Kays, and Peter Nye. 2010. Mining periodic behaviors for moving objects. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 1099--1108.
[46]
Lin Liao, Donald J. Patterson, Dieter Fox, and Henry Kautz. 2007. Learning and inferring transportation routines. Artif. Intell. 171, 5--6 (2007), 311--331.
[47]
Siyuan Liu, Huanhuan Cao, L Li, and MengChu Zhou. 2013. Predicting stay time of mobile users with contextual information. IEEE Trans. Automat. Sci. Eng. 10, 4 (2013), 1026--1036.
[48]
James MacQueen. 1967. Some methods for classification and analysis of multivariate observations. In Proceedings of the 5th Berkeley Symposium on Math, Statistics, and Probability. 281--297.
[49]
George Miller. 1995. WordNet: A lexical database for English. Commun. ACM 38, 11 (1995), 39--41.
[50]
Anna Monreale, Fabio Pinelli, Roberto Trasarti, and Fosca Giannotti. 2009. WhereNext: A location predictor on trajectory pattern mining. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 637--646.
[51]
Raul Montoliu and Daniel Gatica-Perez. 2010. Discovering human places of interest from multimodal mobile phone data. In Proceedings of the 13th International Conference on Mobile and Ubiquitous Multimedia. 12:1--12:10.
[52]
Brendan Tran Morris and Mohan Manubhai Trivedi. 2011. Trajectory learning for activity understanding: Unsupervised, multilevel, and long-term adaptive approach. IEEE Trans. Pattern Anal. Mach. Learn. 33, 11 (2011), 2287--2301.
[53]
Fumitaka Nakahara and Takahiro Murakami. 2012. A destination prediction method based on behavioral pattern analysis of nonperiodic position logs. In Proceedings of The 6th International Conference on Mobile Computing and Ubiquitous Networking. Okinawa, 32--39.
[54]
Donald J. Patterson, Lin Liao, Dieter Fox, and Henry Kautz. 2003. Inferring high-level behavior from low-level sensors. In Proceedings of the 5th International Conference on Ubiqutous Computing. 73--89.
[55]
Susanna Pirttikangas, Kaori Fujinami, and Tatsuo Nakajima. 2006. Feature selection and activity recognition from wearable sensors. In Proceedings of the 3rd International Symposium on Ubiqutous Computing Systems. 516--527.
[56]
Anand Rajaraman and David Ullman. 2011. Mining of Massive Datasets. Cambridge University Press.
[57]
Nishkam Ravi, Nikhil Dandekar, Preetham Mysore, and Michael L. Littman. 2005. Activity recognition from accelerometer data. In Proceedings of the 17th Conference on Innovative Applications of Artificial Intelligence. 1541--1546.
[58]
Philip Resnik. 1999. Semantic similarity in a taxonomy: An information-based measure and its application to problems of ambiguity in natural language. J. Artif. Intell. Res. 11 (1999), 95--130.
[59]
C. Carl Robusto. 1957. The cosine-haversine formula. Am. Math. Mon. 64, 1 (1957), 38--40.
[60]
Olov Rosen and Alexander Medvedev. 2012. An on-line algorithm for anomaly detection in trajectory data. In Proceedings of the American Control Conference. 1117--1122. ACC.2012.6315346
[61]
Bill Schilit, Norman Adams, and Roy Want. 1994. Context-aware computing applications. In Proceedings of the 1st Workshop on Mobile Computing Systems and Applications. 85--90.
[62]
Katarzyna Siła-Nowicka, Jan Vandrol, Taylor Oshan, Jed A. Long, Urška Demšar, and A. Stewart Fotheringham. 2015. Analysis of human mobility patterns from GPS trajectories and contextual information. Int. J. Geogr. Inform. Sci. (2015), 1--26.
[63]
Lu-An Tang, Yu Zheng, Jing Yuan, Jiawei Han, Alice Leung, Chih-Chieh Hung, and Wen-Chih Peng. 2012. On discovery of traveling companions from streaming trajectories. In Proceedings of the 28th IEEE International Conference on Data Engineering. 186--197.
[64]
Alasdair Thomason, Nathan Griffiths, and Matthew Leeke. 2015a. Extracting meaningful user locations from temporally annotated geospatial data. In Internet of Things: IoT Infrastructures. LNICST, Vol. 151. Springer, 84--90.
[65]
Alasdair Thomason, Nathan Griffiths, and Victor Sanchez. 2015b. Parameter optimisation for location extraction and prediction applications. In Proceedings of the 2015 IEEE International Conference on Pervasive Intelligence and Computing. 2173--2180.
[66]
Alasdair Thomason, Nathan Griffiths, and Victor Sanchez. 2016. Identifying locations from geospatial trajectories. J. Comput. Syst. Sci. 82, 4 (2016), 566--581.
[67]
Alasdair Thomason, Matthew Leeke, and Nathan Griffiths. 2015. Understanding the impact of data sparsity and duration for location prediction applications. In Internet of Things: IoT Infrastructures. LNICST, Vol. 151. Springer, 192--197.
[68]
Alessandro Vinciarelli, Anna Esposito, Elisabeth André, Francesca Bonin, Mohamed Chetouani, Jeffrey F. Cohn, Marco Cristani, Ferdinand Fuhrmann, Elmer Gilmartin, Zakia Hammal, Dirk Heylen, Rene Kaiser, Maria Koutsombogera, Alexandros Potamianos, Steve Renals, Giuseppe Riccardi, and Albert Ali Salah. 2015. Open challenges in modelling, analysis and synthesis of human behaviour in human--human and human--machine interactions. Cogn. Comput. 7, 4 (2015), 397--413.
[69]
Jingjing Wang and Bhaskar Prabhala. 2012. Periodicity based next place prediction. In Proceedings of the Nokia Mobile Data Challenge (MDC) Workshop in Conjunction with Pervasive.
[70]
Zhibiao Wu and Martha Palmer. 1994. Verb semantics and lexical selection. In Proceedings of the 32nd Annual Meeting on Association for Computational Linguistics. 133--138.
[71]
Zhengwei Wu, Haishan Wu, and Tong Zhang. 2015. Predict user in-world activity via integration of map query and mobility trace. In Proceedings of the 4th International Workshop on Urban Computing.
[72]
Xiangye Xiao, Yu Zheng, Qiong Luo, and Xing Xie. 2012. Inferring social ties between users with human location history. J. Amb. Intell. Hum. Comput. 5, 1 (2012), 3--19.
[73]
Zhixian Yan, Dipanjan Chakraborty, Christine Parent, Stefano Spaccapietra, and Karl Aberer. 2013. Semantic trajectories: Mobility data computation and annotation. ACM Trans. Intell. Syst. Technol. 4, 3, Article 49 (2013).
[74]
Jiong Yang, Wang Wang, and Philip S. Yu. 2003. Mining asynchronous periodic patterns in time series data. IEEE Trans. Knowl. Data Eng. 15, 3 (2003), 613--628.
[75]
Zhiwen Yu, Hui Wang, Bin Guo, Tao Gu, and Tao Mei. 2015. Supporting serendipitous social interaction using human mobility prediction. IEEE Trans. Hum.-Mach. Syst. 45, 6 (2015), 811--818.
[76]
Daqing Zhang, Nan Li, Zhi-Hua Zhou, Chao Chen, Lin Sun, and Shijian Li. 2011. iBAT: Detecting anomalous taxi trajectories from gps traces. In Proceedings of the 13th International Conference on Ubiquitous Computing. 99--108.
[77]
Kai Zheng, Yu Zheng, Xing Xie, and Xiaofang Zhou. 2012. Reducing uncertainty of low-sampling-rate trajectories. In Proceedings of the IEEE 28th International Conference on Data Engineering. 1144--1155.
[78]
Yu Zheng, Quannan Li, Yukun Chen, Xing Xie, and Wei-Ying Ma. 2008a. Understanding mobility based on GPS data. In Proceedings of the 10th International Conference on Ubiquitous Computing. 312--321.
[79]
Yu Zheng, Like Liu, Longhao Wang, and Xing Xie. 2008b. Learning transportation mode from raw GPS data for geographic applications on the web. In Proceedings of the 17th International Conference on World Wide Web. 247--256.
[80]
Yu Zheng and Xing Xie. 2010. Learning travel recommendations from user-generated GPS traces. ACM Trans. Intell. Syst. Technol. 2, 2 (2010), 2:1--2:29.
[81]
Yu Zheng, Xing Xie, and Wei-Ying Ma. 2010. GeoLife: A collaborative social networking service among user, location and trajectory. IEEE Database Eng. Bull. 33, 2 (2010), 32--39.
[82]
Yu Zheng, Lizhu Zhang, Xing Xie, and Wei-Ying Ma. 2009. Mining interesting locations and travel sequences from GPS trajectories. In Proceedings of the 18th International Conference on World Wide Web. 791--800.

Cited By

View all
  • (2024)Synthesizing Privacy-Preserving Traces: Enhancing Plausibility with Social NetworksPrivacy Preservation in Distributed Systems10.1007/978-3-031-58013-0_2(25-52)Online publication date: 8-Apr-2024
  • (2022)CIME: Context-aware geolocation of emergency-related postsGeoinformatica10.1007/s10707-021-00446-x26:1(125-157)Online publication date: 1-Jan-2022
  • (2019)Next and Next New POI Recommendation via Latent Behavior Pattern InferenceACM Transactions on Information Systems10.1145/335418737:4(1-28)Online publication date: 19-Sep-2019
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Information Systems
ACM Transactions on Information Systems  Volume 35, Issue 2
April 2017
232 pages
ISSN:1046-8188
EISSN:1558-2868
DOI:10.1145/3001595
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 October 2016
Accepted: 01 July 2016
Revised: 01 June 2016
Received: 01 November 2015
Published in TOIS Volume 35, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Clustering
  2. context
  3. land usage
  4. spatiotemporal data
  5. trajectories

Qualifiers

  • Research-article
  • Research
  • Refereed

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)9
  • Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Synthesizing Privacy-Preserving Traces: Enhancing Plausibility with Social NetworksPrivacy Preservation in Distributed Systems10.1007/978-3-031-58013-0_2(25-52)Online publication date: 8-Apr-2024
  • (2022)CIME: Context-aware geolocation of emergency-related postsGeoinformatica10.1007/s10707-021-00446-x26:1(125-157)Online publication date: 1-Jan-2022
  • (2019)Next and Next New POI Recommendation via Latent Behavior Pattern InferenceACM Transactions on Information Systems10.1145/335418737:4(1-28)Online publication date: 19-Sep-2019
  • (2018)A new aspect on P2P online lending default prediction using meta-level phone usage data in ChinaDecision Support Systems10.1016/j.dss.2018.05.001111(60-71)Online publication date: Jul-2018
  • (2016)Predicting interactions and contexts with context treesProceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2996913.2996993(1-4)Online publication date: 31-Oct-2016

View Options

Get Access

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media