{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:04:57Z","timestamp":1760241897881,"version":"build-2065373602"},"reference-count":48,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2018,10,22]],"date-time":"2018-10-22T00:00:00Z","timestamp":1540166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>In this work, we investigate the performance of Markov Chains with respect to modelling semantic trajectories and predicting future locations. In the first part, we examine whether and to what degree the semantic level of semantic trajectories affects the predictive performance of a spatial Markov model. It can be shown that the choice of the semantic level when describing trajectories has a significant impact on the accuracy of the models. High-level descriptions lead to better results than low-level ones. The second part introduces a multi-dimensional Markov Chain construct that considers, besides locations, additional context information, such as time, day and the users\u2019 activity. While the respective approach is able to outperform our baseline, we could also identify some limitations. These are mainly attributed to its sensitivity towards small-sized training datasets. We attempt to overcome this issue, among others, by adding a semantic similarity analysis component to our model that takes the varying role of locations due each time to the respective purpose of visiting the particular location explicitly into consideration. To capture the aforementioned dynamics, we define an entity, which we refer to as Purpose-of-Visit-Dependent Frame (PoVDF). In the third part of this work, we describe in detail the PoVDF-based approach and we evaluate it against the multi-dimensional Markov Chain model as well as with a semantic trajectory mining and prefix tree based model. Our evaluation shows that the PoVDF-based approach outperforms its competition and lays a solid foundation for further investigation.<\/jats:p>","DOI":"10.3390\/s18103582","type":"journal-article","created":{"date-parts":[[2018,10,23]],"date-time":"2018-10-23T08:43:36Z","timestamp":1540284216000},"page":"3582","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Semantic-Enhanced Multi-Dimensional Markov Chains on Semantic Trajectories for Predicting Future Locations"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7939-1408","authenticated-orcid":false,"given":"Antonios","family":"Karatzoglou","sequence":"first","affiliation":[{"name":"Karlsruhe Institute of Technology, 76131 Karlsruhe, Germany"},{"name":"Robert Bosch, Corporate Sector Research and Advance Engineering, 70049 Stuttgart, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"K\u00f6hler","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, 76131 Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Beigl","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, 76131 Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,10,22]]},"reference":[{"key":"ref_1","unstructured":"eMarketer (2018, October 17). Key Trends in Mobile Advertising. Available online: https:\/\/www.statista.com\/statistics\/436071\/location-based-service-users-usa\/."},{"key":"ref_2","unstructured":"Oxford English Dictionary (2018, October 17). Knowledge. Available online: https:\/\/en.oxforddictionaries.com\/definition\/knowledge."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"19052","DOI":"10.1073\/pnas.0800375105","article-title":"A movement ecology paradigm for unifying organismal movement research","volume":"105","author":"Nathan","year":"2008","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_4","unstructured":"Karatzoglou, A., and Beigl, M. (2017, January 12\u201316). Enhancing the Affective Sensitivity of Location Based Services Using Situation-Person-Dependent Semantic Similarity. Proceedings of the 2017 IARIA Eleventh International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies (UBICOMM 2017), Barcelona, Spain."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Karatzoglou, A., K\u00f6hler, D., and Beigl, M. (2018, January 19\u201323). Purpose-of-Visit-Driven Semantic Similarity Analysis on Semantic Trajectories for Enhancing the Future Location Prediction. Proceedings of the 2018 IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops), Athens, Greece.","DOI":"10.1109\/PERCOMW.2018.8480230"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ying, J.J.C., Lee, W.C., Weng, T.C., and Tseng, V.S. (2011, January 1\u20134). Semantic Trajectory Mining for Location Prediction. Proceedings of the 2011 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Chicago, IL, USA.","DOI":"10.1145\/2093973.2093980"},{"key":"ref_7","unstructured":"Ashbrook, D., and Starner, T. (2002, January 7\u201310). Learning significant locations and predicting user movement with GPS. Proceedings of the 2002 IEEE Sixth International Symposium on Wearable Computers (ISWC), Seattle, WA, USA."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Gambs, S., Killijian, M.O., and del Prado Cortez, M.N. (2012, January 10\u201313). Next place prediction using mobility markov chains. Proceedings of the 2012 ACM First Workshop on Measurement, Privacy, and Mobility, Bern, Switzerland.","DOI":"10.1145\/2181196.2181199"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Asahara, A., Maruyama, K., Sato, A., and Seto, K. (2011, January 1\u20134). Pedestrian-movement prediction based on mixed Markov-chain model. Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Chicago, IL, USA.","DOI":"10.1145\/2093973.2093979"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1198\/016214506000001086","article-title":"Mixed hidden Markov models: An extension of the hidden Markov model to the longitudinal data setting","volume":"102","author":"Altman","year":"2007","journal-title":"J. Am. Stat. Assoc."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Ye, J., Zhu, Z., and Cheng, H. (2013, January 2\u20134). What\u2019s your next move: User activity prediction in location-based social networks. Proceedings of the 2013 SIAM International Conference on Data Mining, Austin, TX, USA.","DOI":"10.1137\/1.9781611972832.19"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Mathew, W., Raposo, R., and Martins, B. (2012, January 5\u20138). Predicting future locations with hidden Markov models. Proceedings of the 2012 ACM Conference on Ubiquitous Computing, Pittsburgh, PA, USA.","DOI":"10.1145\/2370216.2370421"},{"key":"ref_13","first-page":"2:1","article-title":"Mining Geographic-temporal-semantic Patterns in Trajectories for Location Prediction","volume":"5","author":"Ying","year":"2014","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Karatzoglou, A., Lamp, S.C., and Beigl, M. (2017, January 9\u201311). Matrix factorization on semantic trajectories for predicting future semantic locations. Proceedings of the 2017 IEEE 13th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Rome, Italy.","DOI":"10.1109\/WiMOB.2017.8115810"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Karatzoglou, A., Sent\u00fcrk, H., Jablonski, A., and Beigl, M. (2017, January 11\u201314). Applying Artificial Neural Networks on Two-Layer Semantic Trajectories for Predicting the Next Semantic Location. Proceedings of the International Conference on Artificial Neural Networks, Sardinia, Italy.","DOI":"10.1007\/978-3-319-68612-7_27"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Karatzoglou, A., Schnell, N., and Beigl, M. (2018, January 4\u20137). A Convolutional Neural Network Approach for Modeling Semantic Trajectories and Predicting Future Locations (to come). Proceedings of the International Conference on Artificial Neural Networks, Rhodes, Greece.","DOI":"10.1007\/978-3-030-01418-6_7"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Karatzoglou, A., Jablonski, A., and Beigl, M. (2018, January 6\u20139). A Seq2seq Learning Approach for Modeling Semantic Trajectories and Predicting the Next Location (to come). Proceedings of the 2018 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, WA, USA.","DOI":"10.1145\/3274895.3274983"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Yao, D., Zhang, C., Huang, J., and Bi, J. (2017, January 6\u201310). SERM: A Recurrent Model for Next Location Prediction in Semantic Trajectories. Proceedings of the 2017 ACM Conference on Information and Knowledge Management, Singapore.","DOI":"10.1145\/3132847.3133056"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1109\/TMC.2005.74","article-title":"A Mobility Prediction Architecture Based on Contextual Knowledge and Spatial Conceptual Maps","volume":"4","author":"Samaan","year":"2005","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_20","unstructured":"Shafer, G. (1992). Dempster-shafer theory. Encyclopedia of Artificial Intelligence, John Wiley & Sons."},{"key":"ref_21","unstructured":"Samaan, N., Karmouch, A., and Kheddouci, H. (2004, January 2\u20135). Mobility prediction based service location and delivery. Proceedings of the Canadian Conference on Electrical and Computer Engineering, Niagara Falls, ON, Canada."},{"key":"ref_22","unstructured":"Samaan, N., Benmammar, B., Krief, F., and Karmouch, A. (2005, January 1\u20134). Prediction-based advanced resource reservation in mobile environments. Proceedings of the Canadian Conference on Electrical and Computer Engineering, Saskatoon, SK, Canada."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Ridhawi, Y.A., Ridhawi, I.A., Karmouch, A., and Nayak, A. (2011, January 10\u201312). A context-aware and location prediction framework for dynamic environments. Proceedings of the 2011 IEEE 7th International Conference on Wireless and Mobile Computing, Networking and Communications (WiMob), Wuhan, China.","DOI":"10.1109\/WiMOB.2011.6085408"},{"key":"ref_24","unstructured":"Ridhawi, I.A., Aloqaily, M., Karmouch, A., and Agoulmine, N. (2009, January 23\u201326). A location-aware user tracking and prediction system. Proceedings of the 2009 Global Information Infrastructure Symposium, Hammemet, Tunisia."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Long, X., Jin, L., and Joshi, J. (2012, January 5\u20138). Exploring Trajectory-driven Local Geographic Topics in Foursquare. Proceedings of the 2012 ACM Conference on Ubiquitous Computing, Pittsburgh, PA, USA.","DOI":"10.1145\/2370216.2370423"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Gandon, F., Sabou, M., Sack, H., d\u2019Amato, C., Cudr\u00e9-Mauroux, P., and Zimmermann, A. (2015). Knowledge Enabled Approach to Predict the Location of Twitter Users. The Semantic Web. Latest Advances and New Domains, Proceedings of the 12th European Semantic Web Conference, Portoroz, Slovenia, 31 May\u20134 June 2015, Springer International Publishing.","DOI":"10.1007\/978-3-319-18818-8"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1111\/j.1469-8137.1912.tb05611.x","article-title":"The distribution of the flora in the alpine zone. 1","volume":"11","author":"Jaccard","year":"1912","journal-title":"New Phytol."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1037\/0033-295X.84.4.327","article-title":"Features of similarity","volume":"84","author":"Tversky","year":"1977","journal-title":"Psychol. Rev."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1016\/j.future.2016.01.012","article-title":"Trajectory ontology inference considering domain and temporal dimensions\u2014Application to marine mammals","volume":"68","author":"Wannous","year":"2016","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_30","first-page":"761","article-title":"Temporal reasoning in trajectories using an ontological modelling approach","volume":"41","author":"Malki","year":"2012","journal-title":"Control Cybern."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Wannous, R., Malki, J., Bouju, A., and Vincent, C. (2013). Time integration in semantic trajectories using an ontological modelling approach. New Trends in Databases and Information Systems, Springer.","DOI":"10.1007\/978-3-642-32518-2_18"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Wannous, R., Malki, J., Bouju, A., and Vincent, C. (2013). Modelling mobile object activities based on trajectory ontology rules considering spatial relationship rules. Modeling Approaches And Algorithms for Advanced Computer Applications, Springer.","DOI":"10.1007\/978-3-319-00560-7_29"},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Wannous, R., Vincent, C., Malki, J., and Bouju, A. (2015). An Ontology-Based Approach for Handling Explicit and Implicit Knowledge over Trajectories. East European Conference on Advances in Databases and Information Systems, Springer.","DOI":"10.1007\/978-3-319-23201-0_41"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Mabroukeh, N.R., and Ezeife, C.I. (2009, January 2\u20136). Using domain ontology for semantic web usage mining and next page prediction. Proceedings of the 2009 CIKM 18th ACM Conference on Information and Knowledge Management, Hong Kong, China.","DOI":"10.1145\/1645953.1646202"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Zhao, Q., Hoi, S.C., Liu, T.Y., Bhowmick, S.S., Lyu, M.R., and Ma, W.Y. (2006, January 23\u201326). Time-dependent semantic similarity measure of queries using historical click-through data. Proceedings of the 2006 ACM 15th international conference on World Wide Web, Edinburgh, UK.","DOI":"10.1145\/1135777.1135858"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.datak.2007.10.008","article-title":"A Conceptual View on Trajectories","volume":"65","author":"Spaccapietra","year":"2008","journal-title":"Data Knowl. Eng."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/s00779-003-0240-0","article-title":"Using GPS to learn significant locations and predict movement across multiple users","volume":"7","author":"Ashbrook","year":"2003","journal-title":"Personal Ubiquitous Comput."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1111\/j.1435-5597.1970.tb01464.x","article-title":"What about people in regional science?","volume":"24","year":"1970","journal-title":"Pap. Reg. Sci."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Yan, Z., Chakraborty, D., Parent, C., Spaccapietra, S., and Aberer, K. (2013). Semantic Trajectories: Mobility Data Computation and Annotation. ACM Trans. Intell. Syst. Technol., 4.","DOI":"10.1145\/2483669.2483682"},{"key":"ref_40","unstructured":"Bishop, C.M. (2006). Pattern Recognition and Machine Learning (Information Science and Statistics), Springer."},{"key":"ref_41","unstructured":"Karatzoglou, A., Ebbing, J., Ostheimer, P., Hua, W., and Beigl, M. (2019). Sentient User modeling Using the Example of Location Prediction (under investigation). User Modeling and User-Adapted Interaction, Springer."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Staab, S., and Studer, R. (2009). Ontology Design Patterns. Handbook on Ontologies, Springer.","DOI":"10.1007\/978-3-540-92673-3"},{"key":"ref_43","unstructured":"W3C (2018, October 17). Defining N-ary Relations on the Semantic Web. Available online: http:\/\/www.w3.org\/TR\/swbp-n-aryRelations\/."},{"key":"ref_44","unstructured":"Minsky, M. (1974). A Framework for Representing Knowledge, Technical Report."},{"key":"ref_45","unstructured":"Minsky, M. (1975). Minsky\u2019s Frame System Theory. TINLAP \u201975, Proceedings of the 1975 Workshop on Theoretical Issues in Natural Language Processing, Association for Computational Linguistics."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Heine, B., Narrog, H., Fillmore, C.J., and Baker, C. (2010). A Frames Approach to Semantic Analysis. Oxford Handbook of Linguistic Analysis, OUP Oxford.","DOI":"10.1093\/oxfordhb\/9780199544004.001.0001"},{"key":"ref_47","unstructured":"Oxford English Dictionary (2018, October 17). Similarity. Available online: https:\/\/en.oxforddictionaries.com\/definition\/similar."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4018\/IJSWIS.2015100101","article-title":"Property-based Semantic Similarity and Relatedness for Improving Recommendation Accuracy and Diversity","volume":"11","author":"Likavec","year":"2015","journal-title":"Int. J. Semant. Web Inf. Syst."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/10\/3582\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:25:28Z","timestamp":1760196328000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/18\/10\/3582"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,22]]},"references-count":48,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2018,10]]}},"alternative-id":["s18103582"],"URL":"https:\/\/doi.org\/10.3390\/s18103582","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2018,10,22]]}}}