Abstract
In the first two decades of this century, the amount of movement and movement-related data has increased massively, predominantly due to the proliferation of positioning features in ubiquitous devices such as cellphones and automobiles. At the same time, there is a vast number of requirements for managing and analyzing these records for economic, administrative, and private purposes. Since the growth of data quantity outpaces the efficiency development of hardware components, it is necessary to explore innovative methods of extracting information from large sets of movement data. Hence, the management and analysis of such data, also called trajectories, have become a very active research field. In this context, the time-dependent geographic position is only one of arbitrarily many recorded attributes. For several applications processing trajectory (and related) data, it is helpful or even necessary to trace or generate additional time-dependent information, according to the purpose of the evaluation. For example, in the field of aircraft traffic analysis, besides the position of the monitored airplane, also its altitude, the remaining amount of fuel, the temperature, the name of the traversed country and many other parameters that change with time are relevant. Other application domains consider the names of streets, places of interest, or transportation modes which can be recorded during the movement of a person or another entity. In this paper, we present in detail a framework for analyzing large datasets having any number of time-dependent attributes of different types with the help of a pattern language based on regular expression structures. The corresponding matching algorithm uses a collection of different indexes and is divided into a filtering and an exact matching phase. Compared to the previous version of the framework, we have extended the flexibility and expressiveness of the language by changing its semantics. Due to storage adjustments concerning the applied index structures and further optimizations, the efficiency of the matching procedure has been significantly improved. In addition, the user is no longer required to have a deep knowledge of the temporal distribution of the available attributes of the dataset. The expressiveness and efficiency of the novel approach are demonstrated by querying real and synthetic datasets. Our approach has been fully implemented in a DBMS querying environment and is freely available open source software.
Similar content being viewed by others
Notes
Note that wgs is a database object of the type \({{{\underline{geoid}}}}\), required for precise computations on the earth’s surface.
The spatial data type \({{{\underline{line}}}}\) represents (a linear approximation of) a continuous curve in the Euclidean plane.
Let dortmund and center be database objects of the types \({{{\underline{region}}}}\) and \({{{\underline{point}}}}\) representing the shape and the city center of Dortmund, respectively.
The leftclosed/rightclosed flags displayed here may vary: In the first case, the interval is lc/rc iff \(\pi _{j-1}\)/\(\pi _j\) is lc/rc; in the second case, the interval is rc iff \(\pi _1\) is not lc; in the third case, the interval is lc iff \(\pi _m\) is not rc.
We assume that london is a database object representing the shape of the city of London.
The spatial region object parc describes the shape of the Parc Naturel Régional de Lorraine.
The script OrderedRelationGraphFromFullOSMImport.SEC is located in the directory secondo/bin/Scripts.
References
Alvares, L.O., Bogorny, V., Kuijpers, B., de Macêdo, J.A.F., Moelans, B., Vaisman, A.: A model for enriching trajectories with semantic geographical information. In: ACM GIS, pp. 22:1–22:8 (2007)
Andrienko, G.L., Andrienko, N.V., Heurich, M.: An event-based conceptual model for context-aware movement analysis. Int. J. Geograph. Inf. Sci. 25(9), 1347–1370 (2011)
Bogorny, V., Renso, C., de Aquino, A.R., de Lucca Siqueira, F., Alvares, L.O.: Constant—a conceptual data model for semantic trajectories of moving objects. Trans. GIS 18(1), 66–88 (2014)
Bracciale, L., Bonola, M., Loreti, P., Bianchi, G., Amici, R., Rabuffi, A.: Crawdad dataset roma/taxi. http://crawdad.org/roma/taxi/20140717 (2014). Accessed 23 Oct 2018
Brinkhoff, T.: A framework for generating network-based moving objects. GeoInformatica 6(2), 153–180 (2002)
Brinkhoff, T.: Network-based generator of moving objects. http://iapg.jade-hs.de/personen/brinkhoff/generator (2002). Accessed 23 Oct 2018
Cai, G., Lee, K., Lee, I.: Discovering common semantic trajectories from geo-tagged social media. In: IEA/AIE, pp. 320–332 (2016)
Camossi, E., Villa, P., Mazzola, L.: Semantic-based anomalous pattern discovery in moving object trajectories. CoRR arxiv:1305.1946 (2013)
Chang, J.W., Song, M.S., Um, J.H.: TMN-tree: new trajectory index structure for moving objects in spatial networks. In: CIT, pp. 1633–1638 (2010)
Damiani, M.L., Issa, H., Güting, R.H., Valdés, F.: Hybrid queries over symbolic and spatial trajectories: a usage scenario. In: MDM, pp. 341–344 (2014)
Damiani, M.L., Issa, H., Güting, R.H., Valdés, F.: Symbolic trajectories and application challenges. SIGSPATIAL Spec. 7(1), 51–58 (2015)
Database Systems for New Applications, Fernuniversität Hagen. http://dna.fernuni-hagen.de/Secondo.html. Accessed 23 Oct 2018
de Almeida, V.T., Güting, R.H., Behr, T.: Querying moving objects in Secondo. In: MDM, pp. 47–51 (2006)
du Mouza, C., Rigaux, P.: Multi-scale classification of moving objects trajectories. In: SSDBM, pp. 307–316 (2004)
du Mouza, C., Rigaux, P.: Mobility patterns. GeoInformatica 9(4), 297–319 (2005)
Erwig, M., Güting, R.H., Schneider, M., Vazirgiannis, M.: Spatio-temporal data types: an approach to modeling and querying moving objects in databases. GeoInformatica 3(3), 269–296 (1999)
Fileto, R., May, C., Renso, C., Pelekis, N., Klein, D., Theodoridis, Y.: The baquara\({}^{\text{2 }}\) knowledge-based framework for semantic enrichment and analysis of movement data. Data Knowl. Eng. 98, 104–122 (2015)
Forlizzi, L., Güting, R.H., Nardelli, E., Schneider, M.: A data model and data structures for moving objects databases. In: ACM SIGMOD, pp. 319–330 (2000)
Geofabrik GmbH and OpenStreetMap Contributors: Openstreetmap data extracts. http://download.geofabrik.de (2007). Accessed 23 Oct 2018
Gryllakis, F., Pelekis, N., Doulkeridis, C., Sideridis, S., Theodoridis, Y.: Searching for spatio-temporal-keyword patterns in semantic trajectories. In: Advances in Intelligent Data Analysis, pp. 112–124 (2017)
Gryllakis, F., Pelekis, N., Doulkeridis, C., Sideridis, S., Theodoridis, Y.: Spatio-temporal-keyword pattern queries over semantic trajectories with hermes@neo4j. In: EDBT, pp. 678–681 (2018)
Güting, R.H., Behr, T., Düntgen, C.: Secondo: a platform for moving objects database research and for publishing and integrating research implementations. IEEE Data Eng. Bull. 33(2), 56–63 (2010)
Güting, R.H., Böhlen, M.H., Erwig, M., Jensen, C.S., Lorentzos, N.A., Schneider, M., Vazirgiannis, M.: A foundation for representing and querying moving objects. ACM TODS 25(1), 1–42 (2000)
Güting, R.H., Schneider, M.: Moving Objects Databases. Morgan Kaufmann, Los Altos (2005)
Güting, R.H., Valdés, F., Damiani, M.L.: Symbolic trajectories. ACM TSAS 1(2), 7:1–7:51 (2015)
Hadjieleftheriou, M., Kollios, G., Bakalov, P., Tsotras, V.J.: Complex spatio-temporal pattern queries. In: PVLDB, pp. 877–888 (2005)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley-Longman Publishing, Reading (2001)
Issa, H., Damiani, M.L.: Efficient access to temporally overlaying spatial and textual trajectories. In: MDM, pp. 262–271 (2016)
Liu, H., Xu, J., Zheng, K., Liu, C., Du, L., Wu, X.: Semantic-aware query processing for activity trajectories. In: International Conference on Web Search and Data Mining, WSDM, pp. 283–292 (2017)
NASA, NGA: Shuttle radar topography mission. https://lta.cr.usgs.gov/SRTM1Arc (2000). Accessed 23 Oct 2018
Navarro, G., Raffinot, M.: Flexible Pattern Matching in Strings—Practical On-Line Search Algorithms for Texts and Biological Sequences. Cambridge University Press, Cambridge (2002)
Newson, P., Krumm, J.: Hidden markov map matching through noise and sparseness. In: ACM SIGSPATIAL, pp. 336–343. ACM (2009)
Nguyen-Dinh, L., Aref, W.G., Mokbel, M.F.: Spatio-temporal access methods: part 2 (2003–2010). IEEE Data Eng. Bull. 33(2), 46–55 (2010)
Nogueira, T.P., Braga, R.B., de Oliveira, C.T., Martin, H.: Framestep: a framework for annotating semantic trajectories based on episodes. Expert Syst. Appl. 92, 533–545 (2018)
Openclipart: https://openclipart.org/ (2018). Accessed 23 Oct 2018
OpenStreetMap Foundation: Openstreetmap. http://www.openstreetmap.org (2004). Accessed 23 Oct 2018
Parent, C., Spaccapietra, S., Renso, C., Andrienko, G.L., Andrienko, N.V., Bogorny, V., Damiani, M.L., Gkoulalas-Divanis, A., de Macêdo, J.A.F., Pelekis, N., Theodoridis, Y., Yan, Z.: Semantic trajectories modeling and analysis. ACM Comput. Surv. 45(4), 42 (2013)
Pelekis, N., Frentzos, E., Giatrakos, N., Theodoridis, Y.: HERMES: a trajectory DB engine for mobility-centric applications. IJKBO 5(2), 19–41 (2015)
Pelekis, N., Theodoridis, Y.: Mobility Data Management and Exploration. Springer, Berlin (2014)
Pfoser, D., Jensen, C.S., Theodoridis, Y.: Novel approaches in query processing for moving object trajectories. In: VLDB, pp. 395–406 (2000)
Quddus, M.A., Ochieng, W.Y., Noland, R.B.: Current map-matching algorithms for transport applications: state-of-the art and future research directions. Transp. Res. Part C Emerg. Technol. 15(5), 312–328 (2007)
Sistemi Territoriali: Roma capitale, mappa dei municipi. http://www.datiopen.it/en/opendata/Municipi_di_Roma_Capitale (2012). Accessed 23 Oct 2018
Spaccapietra, S., Parent, C., Damiani, M.L., de Macêdo, J.A.F., Porto, F., Vangenot, C.: A conceptual view on trajectories. Data Knowl. Eng. 65(1), 126–146 (2008)
Valdés, F., Damiani, M.L., Güting, R.H.: Symbolic trajectories in SECONDO: pattern matching and rewriting. DASFAA 2, 450–453 (2013)
Valdés, F., Güting, R.H.: Index-supported pattern matching on symbolic trajectories. In: ACM SIGSPATIAL, pp. 53–62 (2014)
Valdés, F., Güting, R.H.: Efficient multi-attribute analysis for trajectories: a case study for aircraft. In: ACM SIGSPATIAL, pp. 88:1–88:4 (2017)
Valdés, F., Güting, R.H.: Index-supported pattern matching on tuples of time-dependent values. GeoInformatica 21(3), 429–458 (2017)
Valdés, F., Güting, R.H., Ossi, F.: Efficient trajectory analysis for several time-dependent attributes: a case study for roe deer. In: MDM, pp. 337–340 (2016)
Vazirgiannis, M., Theodoridis, Y., Sellis, T.K.: Spatio-temporal composition and indexing for large multimedia applications. ACM Multimed. Syst. 6(4), 284–298 (1998)
Vieira, M.R., Bakalov, P., Tsotras, V.J.: Querying trajectories using flexible patterns. In: EDBT, pp. 406–417 (2010)
Vieira, M.R., Bakalov, P., Tsotras, V.J.: Flextrack: a system for querying flexible patterns in trajectory databases. In: SSTD, pp. 475–480 (2011)
Vlachos, M., Gunopulos, D., Kollios, G.: Discovering similar multidimensional trajectories. In: ICDE, pp. 673–684 (2002)
Yan, Z., Chakraborty, D., Parent, C., Spaccapietra, S., Aberer, K.: Semantic trajectories: mobility data computation and annotation. ACM TIST 4(3), 49 (2013)
Zhang, C., Han, J., Shou, L., Lu, J., La Porta, T.F.: Splitter: mining fine-grained sequential patterns in semantic trajectories. PVLDB 7(9), 769–780 (2014)
Zheng, K., Shang, S., Yuan, N.J., Yang, Y.: Towards efficient search for activity trajectories. In: ICDE, pp. 230–241 (2013)
Zheng, K., Zheng, B., Xu, J., Liu, G., Liu, A., Li, Z.: Popularity-aware spatial keyword search on activity trajectories. World Wide Web 20(4), 749–773 (2017)
Zheng, Y., Xie, X., Ma, W.: Geolife: a collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull. 33(2), 32–39 (2010)
Zheng, Y., Zhou, X. (eds.): Computing with Spatial Trajectories. Springer, Berlin (2011)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Valdés, F., Güting, R.H. A framework for efficient multi-attribute movement data analysis. The VLDB Journal 28, 427–449 (2019). https://doi.org/10.1007/s00778-018-0525-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-018-0525-6