Keywords

1 Introduction

Mathematically, a trajectory is the path described by a point representing the moving object, usually his center of gravity. In biological sciences, it is the same applied for the living beings as moving objects. In human and social sciences, trajectories may represent the change of the state or the social position of the human being during his life. Modeling and analysis of these trajectories representing the mobility data are important issues to understand the behavior of the moving objects. Accordingly, advantages of mobility-oriented systems are manifold, including: sharing sensors derived status information in on-line social networks, capturing the characteristics and dynamics of everyday activities and enabling queries associated with physical space.

A straightforward idea to deal with this subject is extending the classical DBMS technology to handle such special type of data. Consequently, new technologies taking into account the specificities of such data have emerged. Initially, the DBMSs were extended to consider the specificities of mobility data, which gave rise to the Moving Object Database (MOD). However, current DBMS ability, even with its extensions to support spatio-temporal data, is limited only to storing raw mobility data, represented as a set of spatio-temporal coordinates, which does not include any semantic information. To help researchers make efficient exploitation of this data, many attempts to integrate geographic and application domain knowledge, also referred to as semantic information, have been made to make it more comprehensible, manageable and understandable.

The semantic information added to mobility data could be geographic knowledge, such as application-oriented Points of Interest (PoIs) through which the moving object passes, or its activity during the travel. Activity is actually what the moving objects do at those interesting places, shopping in a mall for example. This natural link between traveling and activities motivates large number of research works to investigate novel approaches for enriching raw GPS data with moving objects’ activities during travel. This could be useful in different applications, such as: social network applications, targeted advertising, public security, town planning and other related applications and services. In the following, we review the main works related to raw trajectory annotation with semantics. Contrary to the previous research works surveying this issue, our paper focuses on methods for computing semantic trajectories, explicitly transforming raw mobility data into meaningful knowledge about semantic trajectories, and introduces a new taxonomy of related work according to used techniques and typology of added semantics.

Accordingly, this paper is structured as follows. The first section, introduces the main concepts related to semantic trajectory modeling issues and presents a taxonomy of the different works tackling semantic enrichment of mobility data. After that, according to the previous taxonomy, we review and discuss related works, classified into three categories: Raw Mobility Data Based Annotation, Static Trajectory Annotation and Dynamic Trajectory Annotation. Finally, we conclude our discussion and present some interesting open issues.

2 Semantic Trajectory Computation: Taxonomy of Related Work

Answering sophisticated queries about trajectory data to understand moving objects’ behavior requires higher level of analysis techniques. In fact, querying raw trajectory data is time consuming and increases the computational and formulation complexity from a user’s perspective seeing that it requires spatial joins. Accordingly, it’s important to start by adding semantic information to raw data, in a preprocessing step. Actually, enriching trajectories with semantic information leads to the discovery of richer and more interpretable semantic trajectory patterns that many data mining techniques, considering trajectories as sample points, may not be able to discover, and facilitates then the understanding of moving object behavior to domain experts.

Various techniques were implemented to enrich raw movement data with semantics. In fact, the addition of semantic information to raw data is referred to as annotation. Typically, the annotation process receives as input mainly raw mobility datasets, and could have in addition any contextual data repository as geographic information. And as output, it produces a set of semantic trajectories, referring to trajectories enriched with semantic information.

The main idea was, at first, introduced by [8]. In this work authors proposed a conceptual modeling approach to associate a layer of semantic information to trajectories. They introduced the trajectory concept as a set of segments: moves [8] (called trips in [7]) and stops [8] (called activities in [7] and stay points in [3]). The latter are essential components of any trajectory of a moving object. A move is defined as a time subinterval where the moving object’s position changes. Stops are, in contrast, time subintervals where the moving object’s position is fixed. Consequently, the process of trajectory annotation requires at first the identification of trajectory components then their annotation with semantic information. In the literature, in overall, two types of semantic information are used to annotate its so called stops and moves:

  • Activities, what mobile objects do during their travel, while moving (moves activities: transportation mode, walking, running, etc.), and when they stop (stops activities: working, shopping, having lunch, etc.). Actually, the inference of an activity depends on the location of the moving object (associated PoI), the time in which it is carried out, its duration, the previous activity performed and other common truth constraints.

  • Geographic information, gathering landmarks, hotspots, building places (museum, mall, restaurant, home, etc.), topography of the land (mountain, lake, etc.) for annotating the stops, and networks (highways, railways, etc.) and streets corresponding to the moving object’s path for annotating the moves. They represent locations of interest or PoIs related to the application domain, whereby the moving object passes or where it stops for a period of time. Moreover, knowing the PoIs associated to the mobile object’s trajectory, one could infer the possible activities practiced on each PoI (working in office, shopping or working in mall, etc.).

The exploitation of trajectories with additional semantic information is a recent but active field. Classically, in order to know what people do during their travels it is possible to ask them to record their activities, as well, it is possible for experts to manually associate semantic information to raw data points using their own words and expressions. This, however, is a tedious and boring task. This is evener more cumbersome when dealing with a large volume of mobility, complemented with the semantic heterogeneity and inconsistency derived from different agents annotating the data with different expressions having same meaning. Therefore, many attempts were made to automate the semantic trajectory computation process using techniques from different fields including machine learning and statistics. In the literature, related work for semantic trajectory annotation is mainly divided into three methods:

  • Raw mobility data based annotation: machine learning and statistics are used to infer moving objects’ activities from raw mobility data without additional semantic information associated. Supervised learning techniques, as Decision Tree (DT) for example, are mostly used to learn how to classify unlabeled data, in our case raw spatio-temporal coordinates, based on a set of labeled data, which are datasets already annotated with moving object’s activities.

  • Static trajectory annotation: geographic information, stored in spatial databases, is explicitly associated to raw mobility data. The joint between geographic information and trajectory spatial coordinates is computed using different techniques in the literature. Then, activities are inferred from the joint geographic information according to domain-related rules. In this case, raw mobility data is annotated with a set of fixed and predefined attributes, this is the reason why we referred to it as a static method.

  • Dynamic trajectory annotation: The use of web resources is becoming more and more widespread all around the world, turning it into an unavoidable source of spatiotemporal information describing the movement and activities of human beings. Consequently, these big amounts of generated mobility-related information are of paramount importance for the understanding of human movement. However, their processing is not a straightforward task. For that, many works in the literature used text mining algorithms to extract space-time semantic information related to human movement from web documents and use it to annotate raw mobility data. We referred to this method as dynamic because added semantics change according to the information provided by social media, which is continuously updated by users.

Once raw mobility data is enriched with semantic information, knowledge discovery and data mining techniques are used to identify behaviors (such as tourist behavior) either from an individual or a group of moving objects’ semantic trajectories. In the following, we discuss related works according to the aforementioned taxonomy of semantic trajectory computation techniques.

3 Raw Mobility Data Based Annotation

In these methods, extracted semantic information is mainly moving object activities such as transportation modes and low-level activities. Activities are recognized based on a set of raw sensor data and without external additional information such as PoIs. This falls within the context of activity recognition research field. In fact, in activity recognition, rules are used to recognize common human or animal’s activities in real life settings. Those rules were beforehand provided by domain experts. Then, researchers started to apply machine learning and statistical algorithms to automate the rules generation task and avoid the expert’s intervention. In the following, we review several related works, addressing this issue, categorized according to the recognized activities.

3.1 Annotation with Transportation Modes

As discussed above, a move is an essential part of a moving object’s trajectory, and as well as a stop, it could be annotated with semantic information in order to describe the activities performed while moving. For recording the movement of human beings, this part is commonly annotated by the transportation modes the moving person uses to travel. Examples of target applications for this contribution are physical activity monitoring, transportation and mobility-based recruitment.

For instance, in [7], a post-processing procedure that takes as input only basic GPS raw data to infer a mobile object’s transportation mode is proposed. The inferred transportation modes are: walking, cycling, in a car, in public transportation and in rail. As a first step, the trips (referring to moves) and activities (referring to stops) are determined. Then, the trips are segmented into single-mode stages. Finally, the transportation mode for each of the stages is identified using a fuzzy logic approach based on speed and acceleration features of the stages.

Differently, in [12] the proposed approach is based on supervised learning to infer users’ transportation modes that could be driving, walking, taking a bus and riding a bike. A change point-based segmentation method is proposed to partition each GPS trajectory into separate segments of different transportation modes. Then, features of each segment are fed to a generative inference model to classify them into one of the transportation modes. The inference model is based on a DT and a bootstrap aggregating employed as a meta-algorithm to improve the accuracy of the model.

Also, in [6] authors introduced a classification system for inferring transportation modes when outside. However, in this work the inferred transportation modes include only: stationary, walking, running, biking and in a motorized transport, and did not distinguish the types of the motorized transportations such as: car, bus, rail, etc., as in the previous works. Moreover, added to the GPS data, authors used an accelerometer to measure acceleration. The used classification system consists of a DT and a first order Discrete Hidden Markov Model (DHMM). Actually, the DT/DHMM combination is considered to be the best accurate since DT is tuned to differentiate between boundaries of transportation modes while DHMM eliminates noise based on temporal knowledge of the transportation mode and the likelihood of transitioning into the next mode.

3.2 Annotation with Low-Level Activities

Many works in the literature used low-level activities to annotate raw mobility data such as: eating, cooking, working on a computer, talking, watching TV, etc. They are generally performed indoor and appeal physical movement with noticeable shift in position and direction of the body members. To be recognized, low-level activities require often, more than the raw time-location data provided by a GPS device, accelerometers tied to different parts of the body, microphones to differentiate between the sitting and watching TV activities for instance, light sensors, etc.

For example, in the work of [4], authors designed and built a multimodal sensor board that simultaneously captured data from seven different sensors: accelerometers, microphone, barometer, etc., gathering real-world activity traces to train activity classifiers. The recognized activities are date-to-date activities such as: walking, climbing stairs, cooking, working on a computer and so on.

Similarly, a user’s activity recognition system is proposed in [2]. The system is based on an algorithm using a classification method to detect 20 physical activities including: brushing teeth, running, walking, watching TV, sitting and relaxing, etc., from data of biaxial accelerometers worn in different parts of the body. The system was tested on different classifiers including base-level and meta-level classifiers from WEKA as: decision table, IBL or nearest neighbor, naive Bayes, etc. The classifiers results are then compared and DT performed the best. In fact, the DT classifier is slow to train but quick to run. Consequently, a pre-trained DT can classify activities in real time quickly.

As in the previous work, the idea in the work of [5] is to recognize activities from triaxial accelerometer formulated as a classification problem. The objective is to analyze the performance of base level classifiers: decision tables, DT, KNN, SVM, naive Bayes, that are integrated in the Weka toolkit, and study the effectiveness of meta model classifiers: boosting, bagging, plurality voting and stacking in improving activity recognition accuracy by combining base-level classifiers. The activities to be recognized are: standing, walking, running, climbing upstairs, climbing downstairs, getups, vacuuming, brushing teeth. Experiments has shown that meta-level classifiers performed better than base-level classifiers, and plurality voting has the best performance.

In the aforementioned works, proposed approaches mainly used classifiers that took as input merely the raw mobility data and does not rely on external spatial/temporal information to infer moving objects’ activities. Most often, DT classifiers showed the best performance. The annotation process starts with the splitting of trajectories into segments of different activities, the features selection and extraction and finally classifier’s training. Generally, in low-level activities recognition, experiments are performed in laboratory settings. Then, it is already known where each activity starts and ends. Therefore, trajectories do not need segmentation as for transportation modes recognition.

In fact, it is non-trivial to accurately extract semantics from only raw mobility data since data requires too much processing before getting to the intended semantics, activities in this case. This also requires a very large amount of it to be processed to avoid noise and unmeaningful results, which might be impossible in some cases where big amounts of data may be unavailable. Therefore, domain prior knowledge as PoIs, social media, rules is required to improve annotation performance and compensate data sparsity. We noticed also the heterogeneity of the inferred activities. Then, a consensus of the research community about location-dependent/user specific models (ontology) would be required to unify the inferred activities.

4 Static Trajectory Annotation

Domain knowledge is represented in many cases as location information: landmarks, PoIs, etc. Such prior knowledge is proved to be helpful in the activity recognition process and improves then its results. In fact, using contextual knowledge about location is sometimes enough to infer coarse level activities. For example, being in restaurant outweighs activities such as eating, taking advantage of the user’s spatial/temporal context to improve inference. In many works in the literature, statistical algorithms are used firstly to identify stops within a trajectory, then each stop is associated to an application-oriented PoI, finally activities are inferred. We refer to such annotation methods here as static.

Authors in [1] proposed a data preprocessing model aiming to integrate trajectories with geographic information. They used firstly the SMoT algorithm to compute stops. In fact, trajectories and geographic data overlap in space. Therefore, exploring trajectory stops is about finding the intersection between trajectory points and application candidate stops, referring to application-related PoIs, where the intersection duration is \(\leqq \) \(\vartriangle _{c}\).

In the work of [10] an approach was proposed to automatically extract sequences of activities from large set of trajectory data and PoIs. They used for that two algorithms with the duplication reuse technique. At first, the Voronoi diagram is used to find subtrajectory parts influenced by a POI. After that, the duration of the influence of a PoI in a subtrajectory is calculated. Then, PAMS (PoI-Activity Mapping Set) provides the rules to map between user activities and PoIs using the calculated influence duration.

Likewise, a general framework for identifying top-k semantic locations significant to users from raw GPS data is introduced in [3]. The first step is to extract stay points, referring to stops, from GPS records based on a threshold duration between two consecutive records. Then resulting stay points are clustered to represent real word semantic locations using a semantic enhanced clustering algorithm SEM-CLS and additional semantic information from geocoded street addresses and yellow pages directory. For ranking the locations, a two layered graph is used for capturing location-location, location-user and location-user relationships using their location histories.

Compared to the first two works, the stops (referred to as stay points) identification method in the last work is more sophisticated appealing clustering, and not just considering the simple intersection between PoIs and trajectories. Clustering, as an unsupervised learning technique, is used in this context for automatically discovering interesting places, associated with stops in trajectories, computed based on density of positions in a spatial area for a certain period of time.

In the aforementioned works, raw mobility data is annotated with semantics (activities or PoIs) coming from predefined databases. Then, semantics used for annotation inhere represent a set of fixed and predefined semantics. However, the semantics of the same location can change according to time.

5 Dynamic Trajectory Annotation

In addition to spatial information as PoIs, semantic information could be represented as temporal information such as information about the event attended at a special location: concert, football game, etc., duration and time of activities: day, hour, weekend, holiday, etc. Added to the large amount of mobility data provided by mobile sensors, nowadays, there is a large-scale of crowd-generated social media data, as location-based social networks, weblogs, e-newspapers among other web resources, that could be used as a source of semantic information about location and time. For that, merging raw mobility data with social media information could help researchers to understand the spatial and temporal semantics of people’s movement. Previous works on semantic trajectory computation used only mobility data and static geographic information to do so. It is only recently that some research works started to focus on merging the aforementioned resources together. We refer to this trajectory annotation method as dynamic since it considers, not only the spatial, but also the temporal semantics of a location.

For example, in the work of [9], researchers proposed a method to annotate the location history of a mobile user using spatiotemporal documents collected from social media e.g. tweets. The proposed system derives for each user’s location history entry a list of words that best describe the purpose of the user’s visit to that location at that time. In fact, researchers in this work annotated user location history with dynamic semantics using techniques from text processing research field. The proposed method for the annotation is time sensitive since that for each location r only documents with time window T are considered. Authors found, after experimentations on a large geo-tagged tweets dataset, that KDE is the more suitable model for annotating mobility data. Actually, the latter captures well the locality and relevance of the words w.r.t a record.

Actually, services could be provided to the user in two ways: location recommendation knowing the activity and activity recommendation knowing the location, to satisfy his information needs for daily routines as trip planning. To do so, authors in [11] modeled a location-activity matrix where each entry is a rating showing how often an activity is performed in a location. The matrix construction is based on users’ GPS history data added to their available comments on the web to identify the activity of the moving object in each visited location according to the following process. The first step is to extract stay points from raw GPS data. Then, stay regions, which are the locations to be recommended, are calculated using grid-based clustering of stay points. Finally, comments attached to GPS points assigned to each of the resulting stay regions are parsed to extract activities. To compensate the sparsity of user-commented locations, authors exploit additional information sources: location features and activity-activity correlations. In this work, activities are extracted manually from comments. This task is too much time consuming, then text mining techniques could be used to automate the annotation process.

Dynamic annotation using social media is considered as a novel method for computing semantic trajectories, since the recent availability of required semantic information on the web. However, there are some improvements which we believe could be beneficial. Firstly, mining the web for extracting annotation words/activities could result in semantic inconsistencies (eating, food, restaurant for the same activity). Then, such proposals require integration of application-related concepts used for annotation (an ontology of activities). Statistical algorithms are used to mine texts in social media. However, social media data is particularly noisy. So treating this type of data requires using the right model to retrieve relevant words with regard to a mobility record. Also, likely proposals, require differentiating between landmark words and event related words using temporal characteristics. Finally, different types of contextual data sources: social media, geographic database, etc. could be used to compensate data sparsity.

6 Conclusion

A wide range of research works have been proposed in the literature to enrich trajectories with semantic information. In this work, we have been motivated by the need to enhance the foregoing attempts to compute semantic trajectories to respond to their limitations. To meet this need, we presented, in this paper, a survey and a taxonomy of the different works on semantic enrichment of trajectory data. The panoply of works proposed in the literature in this issue is consistent and diverse. However, shortcomings were deduced from the different methods presented inhere. Research works, classically, focused on adding spatial semantics to mobility data. Few of the proposed works, mainly dynamic annotation methods using social media, used temporal semantics. Recently, there have been some research efforts for incorporating domain knowledge, represented especially by formal semantics as ontology models, formalized, consensual and generally validated by experts to avoid annotation inconsistencies. In this case, the formality of semantic concepts provided by ontology models permits the automation of the whole process of trajectory semantic annotation going from raw GPS data to semantic trajectories. Also, the use of ontology induces a number of straightforward benefits, explicit semantics, well-defined reasoning mechanisms, great analysis by using warehousing techniques supporting the extraction of valuable information from raw trajectories. However, to the best of our knowledge, little work has been oriented to using ontologies for semantic trajectory computation. Consequently, as future work, we intend to experiment the effectiveness of ontology in helping to encode domain knowledge for computing semantic trajectories. Accordingly, we project to enhance the aforementioned works so that we could provide a complete framework for the construction of semantic trajectories going from raw mobility data to semantic trajectory analysis.