Zhixian Yan
Skip Abstract Section
Abstract
With the large-scale adoption of GPS equipped mobile sensing devices, positional data generated by moving objects (e.g., vehicles, people, animals) are being easily collected. Such data are typically modeled as streams of spatio-temporal (x,y,t) points, called trajectories. In recent years trajectory management research has progressed significantly towards efficient storage and indexing techniques, as well as suitable knowledge discovery. These works focused on the geometric aspect of the raw mobility data. We are now witnessing a growing demand in several application sectors (e.g., from shipment tracking to geo-social networks) on understanding the semantic behavior of moving objects. Semantic behavior refers to the use of semantic abstractions of the raw mobility data, including not only geometric patterns but also knowledge extracted jointly from the mobility data and the underlying geographic and application domains information. The core contribution of this article lies in a semantic model and a computation and annotation platform for developing a semantic approach that progressively transforms the raw mobility data into semantic trajectories enriched with segmentations and annotations. We also analyze a number of experiments we did with semantic trajectories in different domains.
- Alvares, L. O., Bogorny, V., Kuijpers, B., Macedo, J., Moelans, B., and VAISMAN, A. 2007. A model for enriching trajectories with semantic geographical information. In Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems (GIS'07). Google Scholar
Digital Library
- Andrienko, G., Andrienko, N., and Heurich, M. 2011. An event-based conceptual model for context-aware movement analysis. Int. J. Geograph. Inf. Sci. 25, 9, 1347--1370. Google ScholarDigital Library
- Bamis, A., Fang, J., and Savvides, A. 2010. A method for discovering components of human rituals from streams of sensor data. In Proceedings of the 19th ACM International Conference on Information and Knowledge Management (CIKM'10). 779--788. Google ScholarDigital Library
- Beckmann, N., Kriegel, H.-P., Schneider, R., and Seeger, B. 1990. The r∗-tree: An efficient and robust access method for points and rectangles. SIGMOD Rec. 19, 2, 322--331. Google ScholarDigital Library
- Bernstein, D. and Kornhauser, A. 1996. An introduction to map matching for personal navigation assistants. Tech. rep. 8, Princeton University.Google Scholar
- Brakatsoulas, S., Pfoser, D., Salas, R., and Wenk, C. 2005. On map-matching vehicle tracking data. In Proceedings of the 31st International Conference on Very Large Data Bases (VLDB'05). 853--864. Google ScholarDigital Library
- Brinkhoff, T., Kriegel, H.-P., and Seeger, B. 1993. Efficient processing of spatial joins using r-trees. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'93). 237--246. Google ScholarDigital Library
- Buchin, M., Driemel, A., Kreveld, M. V., and Sacristan, V. 2010. An algorithmic framework for segmenting trajectories based on spatio-temporal criteria. In Proceedings of the 18th Annual ACM International Symposium on Advances in Geographic Information Systems (GIS'10). 202--211. Google ScholarDigital Library
- Cao, X., Cong, G., and Jensen, C. S. 2010. Mining significant semantic locations from gps trajectories. In Proceedings of the International Conference on Very Large Data Bases (VLDB'10). 1009--1020. Google ScholarDigital Library
- Chen, S., Jensen, C. S., and Lin, D. 2008. A benchmark for evaluating moving object indexes. Proc. VLDB Endow. 1, 2, 1574--1585. Google ScholarDigital Library
- Forney, G. D. 1973. The viterbi algorithm. Proc. IEEE 61, 3, 268--278.Google ScholarCross Ref
- Frentzos, E. 2008. Trajectory data management in moving object databases. Ph.D. thesis, University of Piraeus.Google Scholar
- Giannotti, F. and Pedreschi, D. 2008. Mobility, Data Mining and Privacy, Geographic Knowledge Discovery. Springer. Google ScholarDigital Library
- Gomez, L. I. and Vaisman, A. A. 2009. Efficient constraint evaluation in categorical sequential pattern mining for trajectory databases. In Proceedings of the 12th International Conference on Extending Database Technology (EDBT'09). 541--552. Google ScholarDigital Library
- Guo, T., Yan, Z., and Aberer, K. 2012. An adaptive approach for online segmentation of multi-dimensional mobile data. In Proceedings of the 11th ACM International Workshop on Data Engineering for Wireless and Mobile Access(MobiDE'12). Google ScholarDigital Library
- Guting, R. H. 2005. SECONDO: A database system for moving objects. GeoInformatica 9, 1, 33--60.Google Scholar
- Guting, R. H., De Almeida, V. T., and Ding, Z. 2006. Modeling and querying moving objects in networks. VLDB J. 15, 2, 165--190. Google ScholarDigital Library
- Guting, R. H. and Schneider, M. 2005. Moving Objects Databases. Morgan Kaufmann, San Fransisco, CA. Google ScholarDigital Library
- Han, J., Lee, J.-G., Gonzalez, H., and Li, X. 2008. Mining massive rfid, trajectory, and traffic data sets (tutorial). In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD'08). Google ScholarDigital Library
- Jun, J., Guensler, R., and Ogle, J. 2006. Smoothing methods to minimize impact of global positioning system random error on travel distance, speed, and acceleration profile estimates. Transport. Res. Rec. J. Transport. Res. Board 1972, 1, 141--150.Google ScholarCross Ref
- Keogh, E., Chu, S., Hart, D., and Pazzani, M. 2004. Segmenting time series: A survey and novel approach. In Data Mining in Time Series Databases, 1--22.Google Scholar
- Kiukkoneny, N., Blom, J., Dousse, O., Gatica-Perez, D., and Laurila, J. 2010. Towards rich mobile phone datasets: Lausanne data collection campaign. In Proceedings of the ACM International Conference Proceeding Series (ICPS'10).Google Scholar
- Kuijpers, B. and Othman, W. 2007. Trajectory databases: Data models, uncertainty and complete query languages. In Proceedings of the 11th International Conference on Database Theory (ICDT'07). 224--238. Google ScholarDigital Library
- Li, Q., Zheng, Y., Xie, X., Chen, Y., Liu, W., and Ma, W.-Y. 2008. Mining user similarity based on location history. In Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS'08). Google ScholarDigital Library
- Li, Z., Ding, B., Han, J., Kays, R., and Nye, P. 2010. Mining periodic behaviors for moving objects. In Proceedings of the 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD'10). 1099--1108. Google ScholarDigital Library
- Li, Z., Han, J., Ji, M., Tang, L. A., Yu, Y., Ding, B., Lee, J.-G., and KAYS, R. 2011. MoveMine: Mining moving object data for discovery of animal movement patterns. ACM Trans. Intell. Syst. Technol. 2, 4, 37. Google ScholarDigital Library
- Lou, Y., Zhang, C., Zheng, Y., Xie, X., Wang, W., and Huang, Y. 2009. Map-matching for low-sampling-rate gps trajectories. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS'09). 352--361. Google ScholarDigital Library
- Marketos, G., Frentzos, E., Ntoutsi, I., Pelekis, N., Raffaeta, A., and Theodoridis, Y. 2008. Building real-world trajectory warehouses. In Proceedings of the 7th ACM International Workshop on Data Engineering for Wireless and Mobile Access (MobiDE'08). 8--15. Google ScholarDigital Library
- Meratnia, N. and Deby, R. A. 2004. Spatiotemporal compression techniques for moving point objects. In Proceedings of the 9th International Conference on Extending Database Technology (EDBT'04). 765--782.Google Scholar
- Mouza, C. and Rigaux, P. 2005. Mobility patterns. GeoInformatica 9, 4, 297--319. Google ScholarDigital Library
- Nanni, M., Trasarti, R., Renso, C., Giannotti, F., and Pedreschi, D. 2010. Advanced knowledge discovery on movement data with the geopkdd system. In Proceedings of the 13th International Conference on Extending Database Technology (EDBT'10). 693--696. Google ScholarDigital Library
- Nergiz, M., Atzori, M., Saygn, Y., and Guc, B. 2009. Towards trajectory anonymization: A generalization-based approach. Trans. Data Privacy 2, 1, 47--75. Google ScholarDigital Library
- Newson, P. and Krumm, J. 2009. Hidden markov map matching through noise and sparseness. In Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS'09). 336--343. Google ScholarDigital Library
- Palma, A. T., Bogorny, V., Kuijpers, B., and Alvares, L. O. 2008. A clustering-based approach for discovering interesting places in trajectories. In Proceedings of the ACM Symposium on Applied Computing (SAC'08). 863--868. Google ScholarDigital Library
- Pelekis, N., Theodoridis, Y., Vosinakis, S., and Panayiotopoulos, T. 2006. HERMES - A frame-work for location-based data management. In Proceedings of the 10th International Conference on Advances in Database Technology (EDBT'06). 1130--1134. Google ScholarDigital Library
- Quddus, M. A., Ochieng, W. Y., and Noland, R. B. 2007. Current map-matching algorithms for transport applications: State-of-the art and future research directions. Transport. Res. Part C: Emerging Technol. 15, 5, 312--328.Google ScholarCross Ref
- Rabiner, L. R. 1990. A tutorial on hidden markov models and selected applications in speech recognition. In Readings in Speech Recognition, 267--296. Google ScholarDigital Library
- Saltenis, S., Jensen, C. S., Leutenegger, S. T., and Lopez, M. A. 2000. Indexing the positions of continuously moving objects. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'00). 331--342. Google ScholarDigital Library
- Schussler, N. and Axhausen, K. W. 2009. Processing gps raw data without additional information. J. Transport. Res. Board 8, 28--36.Google ScholarCross Ref
- Spaccapietra, S., Parent, C., Damiani, M. L., Demacedo, J. A., Porto, F., and Vangenot, C. 2008. A conceptual view on trajectories. Data Knowl. Engin. 65, 126--146. Google ScholarDigital Library
- Wessel, M., Luther, M., and Moller, R. 2009. What happened to bob? Semantic data mining of context histories. In Proceedings of the 22nd International Workshop on Description Logics (DL'09).Google Scholar
- White, C. E., B Ernstein, D., and Kornhauser, A. L. 2000. Some map matching algorithms for personal navigation assistants. Transport. Res. Part C Emerging Technol. 8, 1--6, 91--108.Google ScholarCross Ref
- Wolfson, O., Sistla, P., Xu, B., Zhou, J., and Chamberlain, S. 1999. DOMINO: Databases for moving objects tracking. In Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD'99). 547--549. Google ScholarDigital Library
- Wolfson, O., Xu, B., Chamberlain, S., and Jiang, L. 1998. Moving objects databases: Issues and solutions. In Proceedings of the 10th International Conference on Scientific and Statistical Database Management (SSDBM'98). 111--122. Google ScholarDigital Library
- Xie, K., Deng, K., and Zhou, X. 2009. From trajectories to activities: A spatio-temporal join approach. In Proceedings of the International Workshop on Location Based Social Networks (LBSN'09). 25--32. Google ScholarDigital Library
- Yan, Z. 2010. Traj-ARIMA: A spatial-time series model for network-constrained trajectory. In Proceedings of the 2nd International Workshop on Computational Transportation Science (IWCTS'10). 11--16. Google ScholarDigital Library
- Yan, Z., Chakraborty, D., Parent, C., Spaccapietra, S., and Karl, A. 2011. SeMiTri: A framework for semantic annotation of heterogeneous trajectories. In Proceedings of the 14th International Conference on Extending Database Technology (EDBT/ICDT'11). 259--270. Google ScholarDigital Library
- Yan, Z., Giatrakos, N., Katsikaros, V., Pelekis, N., and Theodoridis, Y. 2011. SeTraStream: Semantic-aware trajectory construction over streaming movement data. In Proceedings of the 12th International Conference on Advances in Spatial and Temporal Databases (SSTD'11). 367--385. Google ScholarDigital Library
- Yan, Z., Macedo, J., Parent, C., and Spaccapietra, S. 2008. Trajectory ontologies and queries. Trans. Geograph. Inf. Syst. 12, 75--91.Google Scholar
- Yan, Z., Parent, C., Spaccapietra, S., and Chakraborty, D. 2010. A hybrid model and computing platform for spatio-semantic trajectories. In Proceedings of the 7th Extended Semantic Web Conference (ESWC'10). 60--75. Google ScholarDigital Library
- Yin, J., Chai, X., and Yang, Q. 2004. High-level goal recognition in a wireless lan. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI'04). 578--584. Google ScholarDigital Library
- Zhang, J. and Goodchild, M. F. 2002. Uncertainty in Geographical Information 1st Ed. CRC Press, Boca Raton, FL.Google Scholar
- Zheng, Y., Chen, Y., Li, Q., Xie, X., and Ma, W.-Y. 2010. Understanding transportation modes based on gps data for web applications. ACM Trans. Web 4, 1. Google ScholarDigital Library
- Zheng, Y., Zhang, L., Ma, Z., Xie, X., and Ma, W.-Y. 2011. Recommending friends and locations based on individual location history. ACM Trans. Web 5, 1, 1--44. Google ScholarDigital Library
- Zheng, Y., Zhang, L., Xie, X., and Ma, W.-Y. 2009. Mining correlation between locations using human location history. In Proceedings of the 17th Annual ACM International Symposium on Advances in Geographic Information Systems (GIS'09). 472--475. Google ScholarDigital Library
- Zhou, C., Frankowski, D., Ludford, P. J., Shekhar, S., and Terveen, L. G. 2007. Discovering personally meaningful places: An interactive clustering approach. ACM Trans. Inf. Syst. 25, 3, 12. Google ScholarDigital Library
Index Terms
- Semantic trajectories: Mobility data computation and annotation
Recommendations
SeMiTri: a framework for semantic annotation of heterogeneous trajectories
EDBT/ICDT '11: Proceedings of the 14th International Conference on Extending Database TechnologyGPS devices allow recording the movement track of the moving object they are attached to. This data typically consists of a stream of spatio-temporal (x,y,t) points. For application purposes the stream is transformed into finite subsequences called ...
Segmentation and Sampling of Moving Object Trajectories Based on Representativeness
Moving Object Databases (MOD), although ubiquitous, still call for methods that will be able to understand, search, analyze, and browse their spatiotemporal content. In this paper, we propose a method for trajectory segmentation and sampling based on ...
Transform-Space View: Performing Spatial Join in the Transform Space Using Original-Space Indexes
Spatial joins find all pairs of objects that satisfy a given spatial relationship. In spatial joins using indexes, original-space indexes such as the R-tree are widely used. An original-space index is the one that indexes objects as represented in the ...
Comments