Excerpt
Tools for Representing Moving Objects and Reasoning on their Semantics: A review
Yuniel E. Proenza Arias
Abstract —The representation and understanding of the move- ment semantics of moving objects is a key issue for developing more accurate and efficient applications for Location Based Services, fleet control and so on. This field became very important for researching in the area of Database and Artificial Intelligence. There are many proposals related with algorithms and techniques for this vein, most of them have been implemented on tools, but they are not in sight of researching community and not available for widely usage. In this paper we present a survey on tools for representing moving objects and reasoning on their movement semantics, analyzing proposals from the database context to recent artificial intelligence ones. Our main goal is to clarify the existence and importance of those unknown tools with high impact on representing moving objects considering the semantics of the movement for spatio-temporal analysis.
Index Terms —moving objects, tools, spatio-temporal analysis, data mining, data models
I. INTRODUCTION
THE constant advances of the computing sciences, the GPS and sensors technologies and the growing necessity of more accurate applications for tracking planes, cars or people have caused researchers to pay special attention to the analysis of the movement semantics, especially to the rep- resentation of movement of spatial entities and the associated reasoning. All these spatial objects that “move or change their shape over time”1 are called moving objects.
Most efforts have been focused on improving Database Management Systems (DBMS) and Query Languages for supporting spatio-temporal information storing and processing. Some studies present techniques to predict trajectories using data mining or indexing. Moreover, with the emergence of the Semantic Web concepts and the known relevance and usefulness of ontologies, some research has run along these lines. The main goal of this article is to review the work done so far in this area, mainly related with the existing tools that implement existing models and techniques of Database and Artificial Intelligence fields.
This work is structured as follow: After the introduction, section II shows important foundations and research moti- vations. Then, section III resumes the comparison of eight selected tools based on stated framework. Section IV shows discussion of obtained results and, finally, section V shows review conclusions and some identified issues for future work.
II. FOUNDATIONS AND MOTIVATION
The analysis of movement semantics has become in an important issue for the correct representation and subsequent reasoning about moving objects in the world (trajectory anal- ysis, movement patterns recognition, movement prediction). Researchers have developed algorithms and techniques needed to face challenges like: finding movement patterns for future movement or change prediction by the analysis of the history of the movement of people or migratory animals, or water level on river margins or inundations; dealing with uncertainty associated with unpredicted movement of birds, wild animals or fish shoals and detecting outlier behaviours using large amounts of data about trajectories stored in a DBMS.
Most of the high developed areas are:
- Conceptual and data models
- Location management
- Trajectory analysis
- Movement patterns recognition
- Outliers detection
- Uncertainty treatment
Examples of conceptual and data models are:2 called the Moving Objects Spatio-Temporal (MOST) data model;3, where Guting et al. present a foundational approach for moving objects algebra (data types and operators) including a limited consideration of lines for trajectory analysis;4, where one proposal of abstract data types for moving points and moving regions is presented;5 called the MADS conceptual model, among others.
The location management allows us to estimate the position of moving objects through time, even of past or future posi- tions (history of movement or movement prediction). Related works are:6, called “Point-in-Polygon Analysis”; Point - Location Management and Trajectory-Location Management, explained in7 ; the Future Temporal Logic (FTL) is the query language for the MOST model and also presented in[2];8 propose some techniques that reduce the problem related with the number of updates needed for analysis, and9, known as Time-parameterized R-Tree (TPR-tree) for indexing the current and predicting future positions of moving objects.
Trajectory analysis is one of the most researched problems on reasoning about moving objects. This field concerns the study of moving entities behaviour, historical information retrieval and other deeper studies. Many applications can be found on car and plane tracking systems, wild life tracking and control, fleet control and so more. In this area, effort has mainly focused on the development of a strong index representation (indexing techniques) and query languages for information retrieval, mining techniques for discovering move- ment patterns and outliers detection. Proposals related with this area are: TraClus10, a trajectory clustering algorithm also called Partition-and-Group Framework; TraClass, proposed in 11 ; Apriori12 and FP-tree13 for mining association rules, among others. Regarding semantic trajectories some proposals are:14, an algorithm called SMoT (Stops and Moves of Trajectories) and15 known as CB-SMoT.
When analysing moving objects data we can find some similarities and frequently common behaviours of data flows over the trajectories. This happens because real life entities (e.g. people, wild animals, cars) sometimes show accustomed behaviours in their movement. All this contributed to the rise of “movement patterns” and their inclusion in the analysis of the semantics present in moving objects trajectories. Relevant works on this vein are:16 which presents DFS MINE algorithm for fast mining of frequent spatio-temporal patterns; 17, where AllMOP and MaxMOP are proposed for discover- ing frequent and maximal patterns over moving objects data, and ObjectGrowth in18.
Related with outliers detection and uncertainty treatment there are some proposals such as:19 ;20, where Lee et al. propose a partition-and-detect framework for trajectory outlier detection;21, known as TOP-EYE;22 ;23, which is a model for representing and querying moving objects trajecto- ries with uncertainty using an indexing structure named TPRU- tree (Time Parameterized R-tree with Uncertainty) and24, where Cheng et al. present a model for uncertainty treatment and Probabilistic Nearest Neighbor Queries (PNNQ).
All the aforementioned techniques have a tremendous im- portance and impact in real-life applications and, given that, a big scientific value for the community. Most of them are only depicted in the papers where they appear, based on experimen- tal results more than in solving real problems. Because of that, scientific community members can not freely experiment with them or apply them on industry or theoretical studies. Actually, some of these techniques have been implemented over tools, mainly focused on aiding in the analysis and understanding of movement semantics. But the knowledge and dissemination of these tools is less than needed, given they are not widely accessible for industry or academy and there is not possible to use them for development or research. Thus, in this work we clarify the existence of such tools, summarizing their most important aspects, such as availability and usability, by a proposed evaluation framework.
III. EVALUATING EXISTING TOOLS
In this section we analyze some existing tools taking into account how, by using them, we can understand movement semantics in a qualitative and feasible manner. On the other hand, it is important to verify if they are available to the research community, which is outstanding in the moving objects researching field.
A. Reference framework for evaluation
Before starting with the evaluation process, we need to state some criteria. Given that the identified software has a diverse nature and intend, we propose some transversal criteria, aiming to be sufficiently taking into account our main objective. The criteria are depicted below.
Usage: Describes the intentionality of the tool (representa- tion, reasoning or both).
Semantic richness: Describes the possibility of including and retrieving of semantic information about moving objects and movement issues, tightly related with the existing tech- niques it implements.
Availability: Describes the tool availability, acquisition fa- cilities and conditions. Also, it comments on the modification permissions under a given license, if possible.
Semantic Scalability: Describes, when it has none or just a little semantic consideration, the possibility of extension for semantic acquisition.
B. MADS tools
These tools are associated to the MADS conceptual model [5]. The three together integrate a suite for creating data models.
MADS Schema Editor
The Schema Editor is the base of the MADS tools, it allows users to model and generate schema definitions for Geograph- ical Information System (GIS) and Database Management System (DBMS). A MADS schema can be constructed in an easy way using the Schema Builder, translated (mapped) to the preferred GIS or DBMS schema using the Schema Translator or modified (updated) or adapted using the Schema Wrappers.
Usage: Representation.
Semantic richness: As it allows the possibility of concep- tual modelling following MADS, it has a moderate semantic richness, given that users can represent some issues related to specific applications, including spatio-temporal aspects, which could be used for enriching trajectories of moving objects, for instance. One problem here is that the selected Database Management System could not support some MADS concepts. On the other hand, Schema Translator itself includes a rich semantic for the mapping process.
Availability: The tool is released under LGPL open source license. Executable or binary file for Linux and Windows, including the source code is available for downloading from http://cs.ulb.ac.be/mads tools/.
Semantic scalability: It can be enhanced if need be, by modifying the source code.
MADS Query Editor
It allows query design over the MADS schema created with Schema Editor. This possibility is enabled only over the initial schema, not to schemas exported to the target application (GIS or DBMS). It helps users to construct their queries in a visual manner. The intent of this tool is to help database managers to understand the MADS schema and query the database easily. It is composed by three more modules: the Query Builder, Query Translator and Query Wrappers. The first is used for visual query formulation and the creation of a MADS expression algebra, which is written into an XML. The second one maps the expression algebra to an intermediate XML format that the last one translates into a Query Languaje (like SQL) for the specified target.
Usage: Reasoning
Semantic richness: The Query Editor allows users to work with the semantics and expressiveness of their queries. It has a visual interface in which the queries can be made by selecting elements.
Availability:Available for downloading from http://cs.ulb.ac.be/mads tools/.
Semantic Scalability:We consider in this case that it is not an important aspect.
MADS Query Viewer
This tool allows the visualization of query results as maps, using a GIS-like system, which displays the necessary ele- ments using maps and tables. Using a slider, the user can analyse the behaviour of the data in a given instant. The map view can be animated for showing real time information.
Usage: Reasoning
Semantic richness: As a visualization tool, it does not include semantics; but plays an outstanding role for the comprehension of the semantics of query results.
Availability: Available for downloading from http://cs.ulb.ac.be/mads tools/.
Semantic Scalability: We consider in this case that it is not an important aspect.
C. SECONDO
It can be catalogued as an extensible DBMS, presented in 25. This is because, even when literature classifies it as an extensible environment for DBMS development, it includes some characteristics that are inherent to this kind of systems. It allows users to develop database systems supporting several data models (including algebras). Some research refers it to as one of the first DBMS considering moving objects. SECONDO has a moving objects component that implements data types and algebra considering moving points and moving regions and allows query execution over these data types. It has a graphical interface implemented in java, which allows moving objects and query results visualization.
Usage: Representation & Reasoning
Semantic richness: One of the main ideas of SECONDO is to include user defined DBMS data models, which could be semantically rich; it makes SECONDO useful “semantically”.
Availability: -
Semantic Scalability: SECONDO supports extensibility by data types and algebras, index techniques and rules, in the last case for example, stating new rules inside the Optimizer (core module). The modular architecture and the programming languages (C++, PROLOG and Java) of its three modules allows modifications.
D. HERMES
Catalogued as a Moving Object Database management sys- tem, HERMES26 provides the necessary infrastructure for representing and querying continuously moving objects. Even so, it can be used for pure spatial or temporal analysis only, which extends its usefulness. Its prototype provides spatio- temporal functionality to Oracle.
Usage: Representation & Reasoning
Semantic richness: Semantically it has little content, given that it maintains the common idea of the current DBMS, but for the spatio-temporal processing capability.
Availability: -
Semantic Scalability: To the best of our knowledge, there is no documentation referring possible modifications into HERMES core directly. But when we analyse the system architecture[89], it is possible to take into account semantic considerations. On the other hand the internal PL/SQL script for querying data can be personalised by the users.
E. MoveMine
It is a data mining interactive tool for spatio-temporal data that includes several kinds of datasets. Implementing some of the most used techniques for spatio-temporal data mining, it allows users to carry out deep analysis over the subjacent data. Movemine supports periodic pattern mining, swarm and convoy pattern mining, trajectory clustering and trajectory outlier detection.
Usage: Reasoning
Semantic richness: Even when it is not possible with this tool to design and execute semantic queries over data, it is possible to analyse results in a very interactive and suitable interface. MoveMine shows results over maps, highlighting most important criteria, drawing paths, which makes possible to researchers or users to understand the meaning of the showed result.
Availability: The system is available over the internet at: http://dm.cs.uiuc.edu/movemine/
Semantic Scalability: To the best of our knowledge there is no way to extend MoveMine.
F. DAMSEL (DAta Mining and Semantic Enrichment query Language)
On27 Trasarti et al. presents DAMSEL, which includes components for integrating reasoning using both, data mining and ontology approaches. It allows design an execution of domain specific queries, trajectory analysis and visualization of the results.
Usage: Reasoning
Semantic richness: As an integration of a data mining query language for spatiotemporal data (Daedalus) and an ontology- based semantic enrichment system (Athena), DAMSEL makes an integrational approach of mining technologies and the se- mantic richness of ontology approaches possible when reason- ing over spatio-temporal data. This integration is materialized when the system is capable of providing a mapping between mined patterns and ontology individuals. Then, new (inferred from mining process) individuals and subsequent information are stored on the ontology, enhancing the inference and reasoning capacity over the information.
Availability: -
Semantic Scalability: The system presents a flexible and scalable architecture, making possible to include new func- tionalities and structure. The Algorithms Manager Component makes possible to include external mining operators in the system. Furthermore, by using the Objects Translator Compo- nent we can integrate new Data objects or new Mining Pattern objects. The ontology contained by the Semantic Package can be enhanced with new concepts, or even make it interoperable with some other ontology or personalized for specific domains. Moreover, using the Rules Integrator Component some user- defined rules can be added according to necessity.
G. WEKA-STPM
In28, Alvarez et al. introduces this extension of WEKA. This extension complements the existing version for spatio- temporal analysis and is considered the first data mining tool for semantic trajectory preprocessing. It is based on two existing methods for trajectory enrichment considering the concept of stop and moves.
Usage: Reasoning
Semantic richness: Includes the analysis using both, IB- SMoT and CB-SMoT algorithms, which allows the reasoning over semantic trajectories.
Availability: It can be downloaded from http://www.inf.ufrgs.br/ alvares/software/
Semantic Scalability: There is not depicted method on WEKA documentation for explicit extension possibilities. On the other hand, as a free and open source tool implemented in java, it is possible to include other existing data mining tech- niques for spatio-temporal analysis of trajectories, including semantic-driven approaches.
H. Comparative summary
Here we present a table that summarises the existing tools evaluation in order to make a comparison between them. Our objective here is to give a global vision for using these tools, taking into account their advantages and disadvantages, strengths and weaknesses. In this case we introduce a qualita- tive metric for semantic richness, aiming to clearly find out the real possibility of semantic treatment of data or models using each tool. The metric have three levels: low (▽), medium (◦) and high (▴). The results of this comparison are shown in Table 1.
Abbildung in dieser Leseprobe nicht enthalten.
SUMMARY AND QUALITATIVE CLASSIFICATION OF EXISTING TOOLS
IV. DISCUSSION
After analyzing existing tools we can state that scientific community have ensured the development of mechanisms for representing moving objects and reasoning considering the movement semantics. Proposals are diverse from database field with data models and specific query languages that consider spatio-temporality to Artificial Intelligence fields that propose techniques for mining common patterns and analyze trajectories and, recently, ontology-driven approaches. Some interesting and important proposals have been implemented
using tools, in most cases for demonstrating the utility and per- formance of a given algorithm. When we consider the spatio- temporal character of moving objects, common paradigms for data models and DBMS should be braked, for that reason exist MADS Tools, Hermes and Secondo. Similar changes have been transforming data mining and indexing approaches, introducing spatio-temporal support and enhanced methods for trajectory analysis; clear examples are TPR-tree, TraClus, SMoT and CB-SMoT, considered in tools like MoveMine and WEKA-STPM.
The most important goal in this research area es to find suitable mechanisms for analyzing moving objects from se- mantic perspective. The poor consideration of semantics on existing models difficult subsequent reasoning. We defend that movement semantics have been considered in somehow and depicted tools allow, in some way, semantic analysis; but this capacity is underdeveloped. Given that, existing techniques and tools are focussing evolution to more descriptive and qualitative character than quantitative one. Having that, we endorse as one of the most innovative and useful proposal to DAMSEL, which integrates data mining, data querying and ontologies, this last element tightly related with semantics.
Even the importance that have the previously mentioned tools, in many cases they are ad-hoc, which makes impossible its extension and usage in related fields beyond depicted in papers. Other real problem is that just few tools are available for using them online or downloading over the internet. The importance of moving objects related fields makes mandatory to explore all available resources aiming to develop suitable proposals, in contrast, the aforementioned situation makes it difficult. That have provoked that most of those tools remain hidden to research community.
V. CONCLUSIONS AND FUTURE WORK
On this work we have surveyed existing tools that im- plements models, techniques or algorithms for representing moving objects and reasoning considering the movement se- mantics. We have stated a reference framework for evaluating them due to estimate their semantic capability, extensibility and availability for the industry or academic community. The necessity of more accurate systems for GIS development, Location Based Services, Forecast Services and some other critical and important fields have stated outstanding goals to researchers in the spatio-temporal and moving objects area. We have found that existing proposals (techniques, models, algorithms) and related tools lack semantic richness. The main interest in this research area is to find how elaborate more qualitative-like queries over spatio-temporal data, and it surely relies over a more qualitative and semantically rich representation. Moreover, we also need to enable the capacity of semantically analyse that spatio-temporal data and relationed reasoning situations in general; in other words, make machines capable to understand the motion semantics as does human reasoning. Existing tools still far of achieving that desired goal. For the future we consider that some integrated approaches should be developed, like DAMSEL that integrates data mining and ontologies. Proposals would include better of each area: the stable data models and support for storing big amount of data and querying the laying information of Databases area; the possibilities of description logics for qual- itative representation and the semantic richness of ontologies and related semantic models. Whichever be the stated proposal it should be available for the research community.
[...]
1 E. Tøssebro and R. Guting, “Creating representations for continuously moving regions from observations,” Advances in Spatial and Temporal Databases, pp. 321-344, 2001.
2 P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao, “Modeling and querying moving objects,” in Data Engineering, 1997. Proceedings. 13th International Conference on. IEEE, 2002, pp. 422-432.
3 R. Guting, M. Bohlen, M. Erwig, C. Jensen, N. Lorentzos, M. Schneider, and M. Vazirgiannis, “A foundation for representing and querying moving objects,” ACM Transactions on Database Systems (TODS), vol. 25, no. 1, p. 42, 2000.
4 M. Erwig, R. Guting, M. Schneider, and M. Vazirgiannis, “Spatio- temporal data types: An approach to modeling and querying moving objects in databases,” GeoInformatica, vol. 3, no. 3, pp. 269-296, 1999. 5 S. Spaccapietra, C. Parent, and E. Zimányi, “Spatio-temporal and multi- representation modeling: a contribution to active conceptual modeling,” Active conceptual modeling of learning, pp. 194-205, 2007.
6 F. Karimipour, M. Delavar, A. Frank, H. Rezayan et al., “Point in
Polygon Analysis for Moving Objects,” in Proceedings of the 4th Workshop on Dynamic & Multidimensional GIS, Gold, C.(ed.), 2005, pp. 5-8.
7 O. Wolfson, “Moving objects information management: The database challenge,” in Next Generation Information Technologies and Systems, ser. Lecture Notes in Computer Science, A. Halevy and A. Gal, Eds. Springer Berlin / Heidelberg, 2002, vol. 2382, pp. 15-26, 10.1007/3- 540-45431-4 7. [Online]. Available: http://dx.doi.org/10.1007/3-540- 45431-4 7
8 A.Čivilis, C. Jensen, J. Nenortaitė, and S. Pakalnis, “Efficient tracking of moving objects with precision guarantees,” 2004.
9 S. Šaltenis,C.Jensen,S.Leutenegger,andM.Lopez,“Indexingthe positions of continuously moving objects,” in Proceedings of the 2000 ACM SIGMOD international conference on Management of data. ACM, 2000, pp. 331-342.
10 J. Lee, J. Han, and K. Whang, “Trajectory clustering: a partition- and-group framework,” in Proceedings of the 2007 ACM SIGMOD international conference on Management of data. ACM, 2007, pp. 593-604.
11 J. Lee, J. Han, X. Li, and H. Gonzalez, “TraClass: trajectory classifi- cation using hierarchical region-based and trajectory-based clustering,” Proceedings of the VLDB Endowment, vol. 1, no. 1, pp. 1081-1094, 2008.
12 R. Agrawal and R. Srikant, “Fast algorithms for mining association rules,” in Proc. 20th Int. Conf. Very Large Data Bases, VLDB, vol. 1215. Citeseer, 1994, pp. 487-499.
13 J. Han, J. Pei, Y. Yin, and R. Mao, “Mining frequent patterns without candidate generation: A frequent-pattern tree approach,” Data mining and knowledge discovery, vol. 8, no. 1, pp. 53-87, 2004.
14 L. Alvares, V. Bogorny, B. Kuijpers, J. de Macedo, B. Moelans, and A. Vaisman, “A model for enriching trajectories with semantic geograph- ical information,” in Proceedings of the 15th annual ACM international symposium on Advances in geographic information systems. ACM, 2007, p. 22.
15 A. Palma, V. Bogorny, B. Kuijpers, and L. Alvares, “A clustering- based approach for discovering interesting places in trajectories,” in Proceedings of the 2008 ACM symposium on Applied computing. ACM, 2008, pp. 863-868.
16 I. Tsoukatos and D. Gunopulos, “Efficient mining of spatiotemporal patterns,” Advances in Spatial and Temporal Databases, pp. 425-442, 2001.
17 T. Vu, J. Lee, and K. Ryu, “Spatiotemporal Pattern Mining Technique for Location-Based Service System,” ETRI journal, vol. 30, no. 3, pp. 421-431, 2008.
18 Z. Li, B. Ding, J. Han, and R. Kays, “Swarm: Mining relaxed temporal moving object clusters,” Proceedings of the VLDB Endowment, vol. 3, no. 1, 2010.
19 T. Cheng and Z. Li, “A Hybrid Approach to Detect Spatial-temporal Outliers,” in Proceedings of the 12th International Conference on
Geoinformatics Geospatial Information Research, 2004, pp. 173-178.
20 J. Lee, J. Han, and X. Li, “Trajectory outlier detection: A partition-and- detect framework,” 2008.
21 Y. Ge, H. Xiong, Z. Zhou, H. Ozdemir, J. Yu, and K. Lee, “TOP- EYE: Top-k Evolving Trajectory Outlier Detection,” In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management (CIKM ’ 10), 2010.
22 G. Trajcevski, O. Wolfson, K. Hinrichs, and S. Chamberlain, “Man- aging uncertainty in moving objects databases,” ACM Transactions on Database Systems (TODS), vol. 29, no. 3, pp. 463-507, 2004.
23 B. Lin, H. Mokhtar, R. Pelaez-Aguilera, and J. Su, “Querying moving objects with uncertainty,” in Vehicular Technology Conference, 2003. VTC 2003-Fall. 2003 IEEE 58th, vol. 4. IEEE, 2004, pp. 2783-2787.
24 R. Cheng, D. Kalashnikov, and S. Prabhakar, “Querying imprecise data in moving object environments,” Knowledge and Data Engineering, IEEE Transactions on, vol. 16, no. 9, pp. 1112-1127, 2004.
25 R. Guting, V. Almeida, D. Ansorge, T. Behr, Z. Ding, T. Hose, F. Hoff- mann, M. Spiekermann, and U. Telle, “Secondo: an extensible dbms platform for research prototyping and teaching,” in Data Engineering, 2005. ICDE 2005. Proceedings. 21st International Conference on, april 2005, pp. 1115 - 1116.
26 N. Pelekis, Y. Theodoridis, S. Vosinakis, and T. Panayiotopoulos, “Hermes-a framework for location-based data management,” Advances in Database Technology-EDBT 2006, pp. 1130-1134, 2006.
27 R. Trasarti, M. Baglioni, and C. Renso, “DAMSEL: A System for Progressive Querying and Reasoning on Movement Data,” in 20th International Workshop on Database and Expert Systems Application. IEEE, 2009, pp. 452-456.
28 L. Alvares, A. Palma, G. Oliveira, and V. Bogorny, “Weka-STPM: from trajectory samples to semantic trajectories,” Proc of the XI Workshop de Sofware Livre, pp. 164-169, 2010.