Which speech organization method moves geographically or in a directional pattern from one physical area to another?

Cartogr Geogr Inf Sci. 2014 May 27; 41(3): 286–307.

Abstract

In geographic information science, a plethora of different approaches and methods is used to assess the similarity of movement. Some of these approaches term two moving objects similar if they share akin paths. Others require objects to move at similar speed and yet others consider movement similar if it occurs at the same time. We believe that a structured and comprehensive classification of movement comparison measures is missing. We argue that such a classification not only depicts the status quo of qualitative and quantitative movement analysis, but also allows for identifying those aspects of movement for which similarity measures are scarce or entirely missing.

In this review paper we, first, decompose movement into its spatial, temporal, and spatiotemporal movement parameters. A movement parameter is a physical quantity of movement, such as speed, spatial path, or temporal duration. For each of these parameters we then review qualitative and quantitative methods of how to compare movement. Thus, we provide a systematic and comprehensive classification of different movement similarity measures used in geographic information science. This classification is a valuable first step toward a GIS toolbox comprising all relevant movement comparison methods.

Keywords: movement comparison, similarity measures, moving objects

Introduction

How similar do two or more objects move with respect to one another? This is an important question in many fields of science in general and in geographic information science in particular (Laube et al. 2007; Vlachos, Gunopulos, and Das 2004). Accordingly, various studies on movement comparison can be found in literature: Dodge, Laube, and Weibel (2012) cluster hurricanes that have reached the shore of the United States between 1907 and 2007 based on the similarity of the hurricanes’ movement across the Atlantic Ocean. Waddington (1979) analyzes three breeds of bees in order to detect similar foraging behavior. Kang et al. (2010) compare the movement of mobile phone users in China. They describe to what degree the mobility patterns of certain age and gender groups differ from one another. Gavric et al. (2011) analyze geo-referenced photos from the online photo sharing platform Flickr that were uploaded by visitors of the city of Berlin. The researchers connect the coordinates of the photos of a single user to spatiotemporal trajectories. Then they cluster similar trajectories to derive those routes in Berlin that are most frequented by tourists who post on Flickr. Interestingly enough, even though all the aforementioned authors aim at quantifying the similarity of their moving objects under study, they do not share a universal concept of how to assess this similarity. Quite the contrary is true. Different authors compare movement with utterly different methods on utterly different physical levels. For Dodge, Laube, and Weibel (2012) two hurricanes move similarly if their paths have similar phases of speed and change of direction of movement. Waddington (1979) considers bees to move similarly if they cover an equal flight distance and change their direction of flight from one flower to another in a similar fashion. For Kang et al. (2010) similar movement of mobile phone subscribers refers to similar average travel distances. Gavric et al. (2011) consider that two tourists move similarly if their paths coincide and connect touristic sights in the same spatial progression. Here, we mention only four different methods on how to assess the similarity of movement, whereas – theoretically and practically – there are a lot more. We want to illustrate this with an example.

In Figure 1, the circle and the square represent two moving objects. At time

Two moving objects in two-dimensional space (x- and y-axis) and time (t-axis).

Lin (1998) defines an intuition for similarity as follows: the more commonality two objects share the more similar they are. Consequently, the more differences they have the less similar they are. The maximum similarity occurs when the two objects are identical.

Now we may take a closer look at movement and its physical quantities, as these are our different ‘levels’ to assess similarity. Without doubt movement bears a temporal dimension; hence one might be interested in comparing movement from a temporal point of view. The circle starts moving before the square and stops after it. Consequently, one conclusion is that the two objects partly move at the same time, in a way that the square is moving during the time when the circle is moving. Accordingly, one might want to know, whether the movement of the two objects is similar from a spatial point of view, as well. In Figure 1, the spatial paths of the circle and the square intersect at

From the example above it may be concluded that movement has a temporal, a spatial and a spatiotemporal dimension. Accordingly, this paper aims at decomposing movement into its physical quantities in time, space, and space-time. Each of these quantities represents one level for which we review measures on how to compare the similarity of movement. In addition to these physical properties of movement, there is also an ‘intrinsic dimension’ of movement: an object moves for a specific purpose, to meet a specific need or fulfill a specific task. Intrinsic movement similarity is briefly discussed where it complements physical similarity, but is generally not part of this paper.

It is quite impossible to cover the entirety of approaches that has been developed in order to assess the similarity of moving objects in a single review. The comparison of movement is important in different fields of science – ranging from biology, to sociology and geography – to name but a few. These fields and their objects under study require very specific similarity measures that are often heavily tailored to the problem under consideration. This results in a plethora of different similarity measures that exist in literature. Nevertheless, we understand our paper as a first step toward a collection of movement similarity measures – that is not complete, but as complete as possible.

The remainder of the paper is organized as follows. Section ‘Related work’ provides an overview on the current state of movement analysis. Section ‘The physical quantities of movement’ decomposes movement into its physical quantities and shows how these quantities are related to each other. Section ‘Comparing movement at different levels’ reviews the most important measures for assessing similarities between movements at different physical levels. Section ‘Summary and conclusion’ summarizes and concludes the results. Section ‘Discussion and future work’ presents the discussion and an outlook on future work.

Related work

Today’s presence of ubiquitous positioning devices allows for collecting detailed traces of movement in space and time. These traces represent a novel data source that requires novel methods for analysis, one of them being measures to assess movement similarity. In this section we discuss literature on movement similarity as well as its relations to other aspects of movement analysis. First, we account for the fact that usually not movement itself but a representation of movement (i.e. a recording of movement) is compared. Then we discuss the quality of these recordings and the influence of the spatial accuracy, sampling rate and uncertainty. Last, we present work that aims at collecting and summarizing methods of movement similarity analysis.

Representing movement

A moving object is any identifiable entity that moves and exists independent of other objects (Macedo et al. 2008). Güting and Schneider (2005) distinguish between two fundamentally different classes of moving objects: objects that maintain a constant shape while moving (e.g. a human being, a vehicle, an animal) and objects that change their shape (e.g. a forest fire). Conceptually, the former are mostly represented as simple point elements, whereas the latter require polygons to model their time-dependent change in extent. As for this paper we exclusively concentrate on similarity measures for point objects.

Movement describes the change of the object’s position in a spatial reference system with respect to time. In real world, change is per se continuous (Sinha and Mark 2005). When a moving object is recorded (e.g. by a Global Positioning System (GPS) logger), only discrete snapshots of the object’s whereabouts are captured and preserved. Andrienko et al. (2008) distinguish between five strategies of how to record snapshots of movement: time-based (a snapshot is recorded after a regular time interval), change-based (a snapshot is recorded when the object changes its position), location-based (a snapshot is recorded when an entity is near a certain spatial location), event-based (a snapshot is recorded when a certain event occurs), and various combinations of these. Depending on which method is used, the same real movement may be represented in entirely different ways.

The resulting representation of movement is called a discrete trajectory. Even though discrete trajectories comprise a non-continuous series of spatiotemporal positions, interpolation can be used to approximate the original, continuous movement. In this case trajectories can be seen as continuous functions from time to space (Andrienko et al. 2008). The fastest and easiest interpolation method is piece-wise linear interpolation (Macedo et al. 2008): a simple straight line connects each two consecutive recorded positions. Along this line the moving object is assumed to move at constant speed. Changes of speed and direction occur abruptly at each position measurement. This is to some extent contrary to real movement where speed and direction change smoothly and gradually. Thus, linear interpolation is not the only way of restoring continuous movement. Other interpolation methods include cubic or high-order polynomial interpolation (Lin, Chang, and Luh 1983). These aim to overcome the shortcomings of linear interpolation.

Entire lifelines and subsequences of movement

In general, most moving objects are dynamic with respect to their surroundings over the whole period of their lifespan. Consequently, Mark and Egenhofer (1998) term trajectories as geospatial lifelines that ‘describe the individual’s location in geographic[al] space’. Different parts along this lifeline are associated with different semantics (Parent et al. 2013). As for living beings, a change in location corresponds to meeting a need: living beings look for food, for a safe place, or a member of the same species to reproduce. Each of these activities lends movement a meaning or purpose. When comparing the movement of two objects, researchers are more often than not interested in assessing the similarities of meaningful subsequences of movement rather than comparing entire geospatial lifelines (Buchin et al. 2009). We want to illustrate this with an example.

When tracking the movement of an albatross (cf. Edwards et al. 2007), the avian lifeline is recorded as soon as the positioning device – in this case a GPS receiver – is attached to the seabird and switched on. Correspondingly, the trajectory ends when the positioning device is switched off and removed from the bird. The domain-expert – i.e. the ornithologist – defines those breakpoints that divide the entire lifeline into legs of specific purpose. For an albatross, a purpose of movement is foraging or migration; therefore, respective breakpoints are stopovers on the ground or departure and return to a nesting habitat. Consequently, the researchers analyze the sub-trajectories that represent foraging or migratory behavior, rather than the entire lifeline of the bird (Spaccapietra et al. 2008). The definition of breakpoints and meaningful sub-trajectories depends on the aim of the research, contextual information as well as expert knowledge. Trajectory segmentation is concerned with finding objective criteria and methods to split entire lifelines into meaningful segments (cf. Buchin et al. 2011; Buchin, Kruckenberg, and Kölzsch 2013).

Spatial accuracy, temporal resolution, and spatial uncertainty

Trajectories allow for recording, representing, and storing the behavior of moving objects in space and time. Moreover, they build the conceptual fundament for movement comparison: we do not assess how similarly two objects move according to their actual behavior in space and time, but according to their measured representation. This implies that the methods used for collecting trajectories have a fundamental impact on similarity assessment. In particular this applies to the spatial accuracy of the measurement device and the temporal resolution of recording. In geographic information science, spatial accuracy defines how closely a measured position matches the real position of a geographic feature in space (Chang 2008). The mean spatial accuracy of a standard GPS receiver, for example, equals 3 meters horizontally at a 95 % confidence interval. 1

Temporal resolution, on the other hand, refers to the update rate of measurements (Longley et al. 2005). For trajectories, it is the time span between recording each two consecutive positions. Temporal resolution affects the spatial path of the trajectory and its uncertainty. Only at measured positions the whereabouts of the moving object are known, the interpolations between these are basically a guess about the actual movement. In general, the lower the temporal resolution, the less certain the whereabouts of the moving objects are known (Pauly and Schneider 2004). In order to quantify spatial interpolation error, Pfoser and Jensen (1999) introduce the concept of uncertainty trajectories. When the maximum possible speed of a moving object is known in advance, several paths may allow the object to leave a known position and arrive at the consecutive one in the allotted time. The union of all these possible paths projected to two-dimensional space results in the so-called uncertainty ellipse. Uncertainty ellipses are defined by two parameters: the maximum speed of the moving object and the temporal resolution of position fixing. Hence, they can be used to guarantee that the spatial uncertainty of the trajectory stays beyond a certain boundary (Ranacher and Rousell 2013). Uncertainty ellipses are valid for unconstrained movement. For an object that is restricted to a network, such as a car to a road network, other methods are applied that re-engineer the most probable path that the object has followed (Zheng et al. 2011).

The fact that sensor measurements are affected by low sampling and error is addressed in the state estimation and target tracking literature (Bar-Shalom, Li, and Kirubarajan 2004; Koch 2010). The approach by Tzavella and Ulmke (2013) utilizes and combines output from particle filtering tracking (sequential Monte Carlo) and GIS techniques. The goal is to infer the actual path of a moving object from sensor measurements which suffer from limited resolution, measurement noise, false alarms, and missed detections due to small target velocity or terrain shadowing.

Movement comparison and movement patterns

Movement pattern analysis is a research field closely related to movement comparison and similarity assessment. Dodge, Weibel, and Lautenschütz (2008) define a movement pattern as ‘a regularity in space or time or any noteworthy relation between movement data’. Movement patterns can be divided into two main classes: they either describe the movement behavior of a single moving object or the relation of two or more moving objects to each other (Jeung, Yiu, and Jensen 2011). Clearly, both types of patterns rely on movement comparison. For finding individual patterns, an object’s movement is compared to itself over time. For group patterns two or more objects are compared against each other. We want to illustrate this with two examples. The individual movement pattern constancy requires that a moving object has a movement parameter that is invariant over time (Laube, Imfeld, and Weibel 2005). The individual pattern ‘constancy of speed’ can be rephrased as a simple comparison: ‘Which objects exhibit a similar speed during their entire movement?’ The group pattern moving cluster requires objects to move close to one another for a certain time span (Gudmundsson and van Kreveld 2006; Kalnis, Mamoulis, and Bakiras 2005). In order to detect whether two objects qualify as a moving cluster, their paths have to overlap and occur at the same time. A structured overview on movement patterns can be found in Dodge, Weibel, and Lautenschütz (2008).

Movement comparison

An extensive literature review on movement similarity measures is presented by Dodge (2011) in the form of an introductory section to a PhD thesis. However, this review mainly focuses on quantitative measures. Purely qualitative measures are not covered. Long and Nelson (2012) review qualitative and quantitative methods for analyzing movement data. They briefly discuss the topic of movement similarity, their main focus, however, lies on a general review of movement analysis. Other – more or less extensive – reviews of movement similarity measures are often found in the related work section of articles that introduce novel similarity measures. Frentzos et al. (2008) provide a short overview on similarity research for trajectories and mention the need for further similarity measures. Dodge, Laube, and Weibel (2012) divide methods for assessing the similarity of moving objects into two classes: spatial similarity and spatiotemporal similarity. Spatial similarity methods fall back on the spatial path and its shape as the only comparable measures to check whether two trajectories are similar; accordingly, spatiotemporal similarity methods compare movement with respect to spatial as well as temporal aspects. In spite of all the literature mentioned above, to the best of our knowledge an exhaustive literature review is missing that

• focuses on the classification of movement similarity measures;

• distinguishes between qualitative – or topological – and quantitative approaches;

• and explains for which data sets and tasks the measures are used.

The physical quantities of movement

Dodge, Weibel, and Lautenschütz (2008) propose a set of characteristic features of movement, which they refer to as movement parameters. A movement parameter is an inherent physical quantity of movement, such as the duration of the movement or its speed. Similar to Dodge, Weibel, and Lautenschütz (2008), we decompose movement into its physical quantities. These represent the different levels at which movement is compared. Movement parameters are either primary ones and refer to a distinct position in an absolute reference system, or derived and indicate the relative change between two primary parameters. Consequently, primary movement parameters are measured, whereas derived movement parameters are calculated from one or more measurements. Figure 2 shows all primary movement parameters. The distinction between primary and derived movement parameters is important for finding applicable measures of how to compare movement and how to interpret their results. The following section recaps the most important primary and derived movement parameters.

Primary movement parameters in time, space, and space–time.

Temporal movement parameters

Temporal movement parameters describe when, for how long, how often, and how regular an object is moving. The principal measurement in the temporal dimension is a time instance (

A temporal duration

Spatial movement parameters

Spatial movement parameters describe where, how far, and in which direction an object is moving. The principal spatial observable is a spatial position that a moving object attains. In two dimensions, a spatial position is defined as

The position difference

In order to describe the distance between two positions along a spatial path two different distance concepts are applied: the range between two positions

The sum of all consecutive position difference vectors results in the shape of the spatial path. Shape is independent of an absolute position in a reference system. It can be expressed by other derived parameters such as sinuosity, curvature, tortuosity, curviness, or fractal dimension. Each of these – in some way or the other – depicts the degree of ‘winding’ of a path. Sinuosity, for example, relates travelled distance to range. For a detailed definitions of sinuosity, curvature, curviness, and tortuosity, see Buchin et al. (2011). Fractal dimension measures to what degree a path ‘fills’ the space it is roaming in (Mandelbrot 1983): a straight line fills space least, whereas an entirely random motion fills it most.

Comparing movement at different levels

This section reviews the most important concepts of how to compare the movement of two or more objects. Each physical quantity of movement discussed in section ‘The physical quantities of movement’ represents one level of comparison. In addition to these we introduce three criteria that define the type of similarity measure.

Types of similarity measures

The following three criteria are used to distinguish between different types of similarity measures:

• Is the measure applicable for primary or derived movement parameters?

• Does the measure rely on a topological or quantitative comparison of movement?

• What is the measure intended and/or mainly used for?

The three criteria are discussed in this section together with the types of similarity measures they define.

Similarity measures for primary and derived movement parameters

In section ‘The physical quantities of movement’ we distinguish between primary and derived movement parameters. Consequently, we also divide similarity measures into those for primary movement parameters and those for derived movement parameters. For simplicity these are henceforth referred to as primary and derived similarity measures. Primary similarity measures compare the movement of two objects with respect to their positions in a temporal, spatial, or spatiotemporal reference system. An example for a temporal reference system is the Gregorian calendar, a spatial one is the World Geodetic System 1984 and a spatiotemporal the space–time cube (see also, Kraak 2003). In these reference systems, two objects might move similar to each other with respect to (i) time, (ii) space, or (iii) space–time. For (i) they share the same spatial path, for (ii) they move at the same time, for (iii) they share the same path at the same time. In other words, movement that is similar with respect to its primary parameters occurs at similar times or occupies similar space. Correspondingly, derived similarity measures compare movement with respect to those characteristics that are independent of a spatiotemporal reference frame. Two objects might move for the same duration or have a similar speed without sharing similar paths or moving at the same time.

Topological and quantitative similarity

The second criterion classifies a measure as topological or quantitative. According to Price (2013), topology is concerned with the study of qualitative properties of certain objects. It is a mathematical concept that allows for structuring data based on the principles of feature adjacency and feature connectivity. A topological relation is preserved if the object is rotated, scaled or translated (Rinzivillo, Turini, et al. 2008). Topological relations may also be termed qualitative relations. However, the key publications reviewed for this paper mostly use the more specific term topological relations. Hence, this term is also adopted in this paper. When a qualitative relation does not qualify as a topological one, this is mentioned specifically. For two moving objects, topological similarity measures describe how the movement parameters of these objects relate to each other without taking into account any quantitative consideration. Thus topological similarity measures help to answer questions such as: ‘Do the spatial paths of the objects intersect?’, ‘Do the objects move during the same time?’, ‘Do the objects move away or towards one another?’

Quantitative similarity allows for expressing relations of two moving objects in terms of numbers that can be calculated or measured. Thus, it allows for answering questions such as ‘How far are the objects away from each other in space?’, ‘How close are the trajectories of these objects in space and time?’ Quantitative or non-topological similarity is usually associated to a distance function. Distance functions are either metric or non-metric. A metric distance function

• non-negative

  
  ;

• unique

  
  ;

• symmetric

  
  ;

• and satisfies the triangle inequality (Chaudhuri and Rosenfeld 1996).

Simple Euclidean distance is an example for a metric measure. A non-metric measure is the longest common subsequence (LCSS) described in section ‘Spatiotemporal trajectory’.

Purpose of the similarity measure

This criterion defines the purpose for which the similarity measure is intended or mainly used for. We distinguish between four types of purpose:

• description – the measure explains or formalizes a relation between the two moving objects;

• clustering – the measure is used to group similar moving objects;

• similarity search – the measure finds most similar moving object with respect to a reference object;

• behavior analysis – the measure describes the behavior of one object with respect to another;

• outlier detection: the measure identifies unusual behavior in a set of data.

Of course, these criteria are overlapping and should not be understood as exclusive. A measure that is used for clustering also allows performing a similarity search. Moreover, it is based on a formalized relation between two movement parameters.

In addition to these three criteria, we give examples of data sets to which the respective measure is or may be applied. Moreover, we add the computational complexity of the measure: low refers to linear or quasilinear complexity, medium to quadratic complexity, and high to polynomial or higher complexity. However, this classification is neither meaningful nor possible for all measures. First, some measures are only defined theoretically and are not implemented algorithmically. For these computational complexity is not explicitly mentioned. Second, for some measures there exist heuristics that may considerably improve the computational complexity, but retrieve non-optimal results. In addition to this, complexity may relate to the comparison of an entire data set (i.e. clustering), or to the comparison of two entities in the data set.

In the following section the different similarity measures are discussed.

Temporal similarity measures

Temporal similarity measures are based on either a linear or a cyclic concept of time (Luisi 1999): linear time flows continuously from the past to the future. Time instances refer to an exact position along this time flow, similar to a number on a number ray. Consequently, two time instances are equal if they occur at the same position along this time flow. Any arbitrary time instance may serve as an origin for a temporal reference system based on linear time. For example, GPS uses the time instance 0h UTC, January 5 1980 as a time zero point (Lewandowski and Thomas 1991). If time is considered cyclic, it is assumed to ‘repeat’ after a certain temporal interval. This interval is most intuitively related to the Earth’s rotation around its own axis (day) or the sun (year); other intervals follow human concepts related to Earth rotation (week, month, decade). In cyclic time, two time instances are equal if they occur at the same temporal position during one cycle, i.e. if a well-defined interval has passed between them: whereas January 1 2012 is distinct from January 1 2013 in linear time, these dates are equal in a time concept based on the annual cycle.

Time instance

Time instances are positions in a temporal reference frame; hence they require primary similarity measures. A topological relation between two time instances

The temporal distance between

Temporal interval

In contrast to zero-dimensional time instances, temporal intervals cover a certain temporal extent; they are essentially one-dimensional line objects in one-dimensional temporal space. Therefore they require slightly more complex topological relations. Allen proposes a qualitative temporal logic with a complete set of 13 distinct relations between two temporal intervals (Allen 1983). Figure 3 shows three temporal relations between

Three examples for Allen’s temporal logic (based on Allen 1983).

Fox, Glahder, and Walsh (2003) analyze the spring migration of geese from Ireland to Greenland. Their data suggest that some birds start their passage earlier in autumn and arrive to Greenland later than other birds. Translated into Allen’s temporal logic, the migratory movement of the ‘faster’ birds occurs during that of the ‘slower’ ones.

Each time interval comprises a start and an end time instance. The temporal distance between respective end and start time instances results in a quantitative measure of how the temporal intervals are different. In the above-mentioned research on migratory geese, one ‘fast’ goose leaves Ireland three days after another ‘slower’ one, but reaches the shores of Greenland about ten days before.

Temporal duration

Temporal duration refers to the time span of one meaningful leg of movement. Temporal duration is a derived measure. In a qualitative (topological) way, two durations can be compared with the well-known set of relational operators ‘=’ (equal duration), ‘<’ (shorter duration), and ‘>’ (longer duration). A quantitative measure is the difference between two durations. Ueta et al. (2000) track the movement of adult and juvenile sea eagles. They find that the migratory movement of adults lasts shorter than that of their younger conspecific.

Spatial similarity measures

Spatial position

The topological comparison of two spatial positions is trivial: the two positions either intersect or do not intersect (Egenhofer and Herring 1991). Girardin et al. (2008) analyze the spatial occurrence of mobile phone calls to reason about the movement of tourists in the city of Rome. A tourist’s mobile phone call stands for one discrete spatial and temporal presence of the tourist. Wherever a sufficient number of tourists are sensed, the researchers identify a touristic hotspot. A hotspot is essentially a location in the city of Rome, where the call positions of many tracked tourists intersect. In avian migration, stopover locations represent one important spatial position along the birds’ migratory path. In a study on crane passage from Russia to China, Higuchi et al. (1996) find that the demilitarized zone between North and South Korea hosts a major stopover site for their birds under study. Here, the individual stopover locations of the birds intersect. (Note: whether a hotspot is interpreted as a point or an area largely depends on the aim of the analysis and on scale. For reasons of simplicity, here, a hotspot is viewed as a point.)

A quantitative relationship of spatial positions is the spatial distance between them. A spatial distance function describes how far two points are away from each other in space. Obviously, spatial distance strongly relies on the underlying reference system, its characteristics and dimensionality. Intuitively, the most common distance function is Euclidean distance, which describes the length of the straight line between two points in Euclidean space. Euclidean distance is, but a special case of the more general Minkowski distance. Minkowski distance is calculated as

Distance measures for reference systems other than Euclidean, comprise distances along curved surfaces (such as the spherical distance on a globe and the spheroidal distance on an ellipsoid), or network distances. In a network, a cost function represents the effort it takes to pass a path between two nodes. The cost value might refer to the length of that path in terms of Euclidean distance, as well as the time or an abstract cost needed to traverse the path (Hofmann-Wellenhof, Legat, and Wieser 2003). In a road network, costs may – for example – represent a car’s expected fuel consumption (Minett et al. 2011). Depending on the cost function, network distance is a metric (Euclidean distance) or a not a metric (e.g. fuel consumption).

In two-dimensional Euclidean space a moving object has two degrees of freedom. Consequently, spatial distance is not the only measure of how to compare two spatial positions: we lack information on the spatial direction of this distance. In Euclidean space, direction is expressed as the unit vector of the distance vector between the two positions. The relative direction of the unit vector with respect to a reference vector (e.g. a coordinate axis) yields a quantitative angular measure (e.g. 90°) (Hofmann-Wellenhof, Legat, and Wieser 2003). Frank (1996) introduces a qualitative – but not topological – method for comparing directional information based on the cardinal directions in a compass. He suggests different approaches to partition space based on the observer’s position: cardinal directions of cones (North, West, South, East), of half planes (Northwest, Northeast, Southwest, Southeast) and directions with a neutral zone at the location of the observer (North, Northwest, West, Southwest, South, Southeast, East, Northeast, and neutral zone) (Frank 1996).

In an analysis on avian migration Chevallier et al. (2011) identify the stopover locations of black storks on their flight from Europe to Africa in autumn and vice versa in spring. The researchers find that the stopover locations of individual birds do not match for spring and autumn migration. For instance, the tracked bird named Aurelia has its longest spring stopover in Spain approximately 83 km (spherical distance) North of its autumn stopover.

Spatial path and line

The 9-intersection model describes the different topological relationship between the interior (

Depending on the measurement device and the sampling strategy a qualitative comparison of spatial paths might be unrealistic. Two paths recorded by GPS in a time-based manner will hardly ever exactly intersect. In order to allow for qualitative analysis the underlying space has to be discretized. Locations that are spatially close are aggregated into one area; topologically this area is then again treated as one single spatial position. On the one hand, a discretization of space may follow from the sampling strategy used for recording movement. Two examples for sampling strategies that discretize space are event-based recordings in a mobile phone network (cf. Calabrese et al. 2011; Calabrese et al. 2010; Girardin et al. 2008; González, Hidalgo, and Barabási 2008) and location-based recording with Bluetooth scanners (cf. Versichele et al. 2012). In both cases the position of the static sensor (base transceiver station or Bluetooth scanner) is used to indicate the position of an object that is close to the sensor. Thus the network itself divides space into discrete areas comprising the sensor and its vicinity (in a mobile phone network referred to as a cell). On the other hand researchers might discretize space into areas according to knowledge gained from the movement (Andrienko et al. 2011; Andrienko and Andrienko 2010) or knowledge they have about space (e.g. due to territorial units).

Independent of similarity in real space, movement may occupy an abstract feature space (cf. Andrienko et al. 2013). Abstract space is relevant in the field of human activity recognition, i.e. research aiming at inferring human activities from movement traces (Furletti et al. 2013; Liao et al. 2006; Sadilek and Kautz 2010). Two human beings travelling from home to work and then to a restaurant may visit utterly different locations in real physical space. In an abstract activity space these locations nevertheless intersect. Semantically two homes, two workplaces, and two restaurants are the same: locations for living, working, and eating. Hence in abstract space, a qualitative analysis of the two paths is feasible.

Figure 4 shows three examples for 9-intersection relations between two paths. In (a) the paths entirely intersect; in (b) the start end positions intersect, whereas the interior of the paths do not; in (c) only the interior of the paths intersect. For reasons of better readability

Three examples for a 9-intersection relation between two paths based on Egenhofer and Herring (1991).

Versichele et al. (2012) install a system of static Bluetooth scanners to monitor the movement of visitors of a cultural festival in the city of Ghent. Visitors who follow the same (sub-)path from one Bluetooth scanner to the other could be interpreted as one of the 9-intersection relations, i.e. relation (c) in Figure 4.

Gruteser and Hoh (2005) equip students at the State University of New Jersey with GPS receivers and monitor their movement. One of their (obvious) observations is that the students’ paths intersect at the University Campus (cf. relation (a) in Figure 4).

For paths that occur in a non-discretized space, quantitative comparison measures play a far more important role, especially in the field of (time-relaxed) trajectory clustering. Trajectory clustering finds those objects that move close to one another in space (time-relaxed) or space–time (time-aware). In order to quantify spatial closeness, clustering relies on a specific distance measure. We distinguish between two different types of distance measures for paths: either the similarity measures account for the entire path (global measures) or only some segments of the path (local measures).

Global path similarity

A simple and straightforward measure for comparing two paths is the Euclidean distance between the two pairs of respective boundary positions, i.e. the distance between the two origins (

If every (recorded) spatial position of a path is considered a checkpoint, the resulting distance is referred to as the Euclidean distance between two paths (Zhang, Huang, and Tan 2006). Euclidean distance requires two paths to have the same number of spatial positions. Generally, it is of quadratic computational complexity. Cai and Ng (2004) propose a computationally fast approximation of Euclidean distance between two paths. They apply it to retrieve the similarity of hockey players’ movement on the pitch.

The common route distance (Andrienko, Andrienko, and Wrobel 2007) continuously searches two paths for positions that spatially match, that are within a certain distance threshold of each other. It calculates the mean Euclidean distance between matching positions and a penalty distance for positions that do not match. Hence, its computational complexity is also quadratic. Common route distance can handle incomplete and faulty data, due to its relative insensitivity to outliers. As it does not satisfy the symmetry axiom, common route distance is not a metric. However, it becomes a metric if modified to

Junejo, Javed, and Shah (2004) apply a distance function based on Haussdorff distance for finding similar paths of people moving in video surveillance scenes. For two spatial paths

Pelekis et al. (2012) propose the locality in between polylines (LIP) distance function. LIP calculates the area between two paths on a Cartesian plane; it is used by the authors for clustering vehicle GPS data in space. LIP may express the global similarity between two paths as well as the local similarity. LIP is comparably fast and has quasilinear computational complexity. It is not a metric but becomes one if modified to

Lin and Su (2005) propose a distance measure between two paths called the one-way distance (OWD). OWD from the path

Local path similarity

For local path similarity, a path is considered a segment of simple lines, where one line connects consecutive spatial positions. Rather than the entire path, some sub-segments comprising one or several lines are analyzed for similarity, whereas others are simply not considered.

Lee, Han, and Whang (2007) combine three types of distance measures to assess the similarity of two lines: angular distance, perpendicular distance, and parallel distance. Let

Bashir, Khokhar, and Schonfeld (2003) use principal component analysis (PCA) to cluster matching paths in video retrieval scenes. Their approach concatenates the spatial positions of a path into a one-dimensional signal. Then, PCA filters out those coefficients of the path that are most important, i.e. that contribute most to the path’s variance. In a last step, the Euclidean distance between these remaining coefficients is calculated.

Travelled distance and range

Travelled distance and range are derived measures of movement. Hence, the topological relations of comparison are given by the relational operators ‘=’ (equal travelled distance/range), ‘<’ (shorter travelled distance/range), and ‘>’ (longer travelled distance/range). A quantitative means of comparison is the difference between travelled distance/range.

Travelled distance and (home) range play an important role in ecology and research on human mobility. Merrick and Loughlin (1997) compare the travelled distance and the home ranges of foraging stellar sea lions in Alaska. Mate, Nieukirk, and Kraus (1997) track the movement of whales in the North Atlantic and compare their travelled distances. Tøttrup et al. (2012) record the annual migration cycle of red-backed shrike from Europe to Africa and find that during spring migration the birds travel a 1/5 longer distance, as they take a detour over the Persian Peninsula. González, Hidalgo, and Barabási (2008) study the spatial occurrence of mobile phone calls of mobile phone subscribers. They calculate the step size (or travelled distance) between each two calls of one user and find that overall human displacement is highly predictable. Moreover, they calculate and compare the mobile phone users’ radii of gyration, a measure that corresponds to a range from the trajectories’ center of gravity.

Heading

Heading indicates the relative direction toward which an object moves. If heading is interpreted as an angular measure, it may be compared in a topological manner with the three relational operators: ‘=’ (same angle), ‘<’ (smaller angle), and ‘>’ (bigger angle). Moreover, the difference between angles can be calculated. This difference can be interpreted in a qualitative manner: if object A moves at a difference of around 180° with respect to B, the two objects are said to move into opposite directions. If relative direction is interpreted in the sense of a cardinal direction (cf. Frank 1996) two relations suffice for comparison: ‘=’ (same cardinal direction) and ‘

Melnychuk, Welch, and Walters (2010) track migrating salmon and study their heading after entering the ocean. They find that salmon from two different rivers tend to migrate into opposite cardinal directions: the one swim North, the others South. Laube and Imfeld (2002) and Laube, Imfeld, and Weibel (2005) use heading as one parameter in their REMO analysis concept. They apply REMO to caribou GPS data in order study their behavior. They find that during spring the caribous head mostly to North and Northeastern direction, whereas in summer they rather tend toward South and East.

Pelekis et al. (2007) develop a computationally fast measure to compare the consecutive headings of two moving objects along their path. The differences between these result in the overall directional similarity between the two movements. They apply their algorithm to find similar vehicle GPS trajectories.

Shape

Shape describes how a moving object ‘winds’ its way through a spatial reference system. Shape similarity is expressed as a qualitative (topological) or quantitative relation of the shape parameter under consideration, i.e. sinuosity, curvature, tortuosity, curviness, and fractal dimension. Without neglecting the semantic differences between these, we henceforth use sinuosity as a proxy for all. Again, the relational operators ‘=’ (equal sinuosity), ‘<’ (smaller sinuosity), and ‘>’ bigger sinuosity represent the topological relations, whereas a quantitative relation is given by the difference between two sinuosity measures.

In biology the sinuosity of an animal’s path is a key measure for classifying searching behavior. It helps researchers to distinguish between a planned, oriented, and effective behavior (low sinuosity) and a random search behavior (high sinuosity) (Benhamou 2004). Focardi, Marcellini, and Montanaro (1996) study the movement of deer and infer different foraging behavior from the sinuosity of their paths. The degree of winding of a path is also used to reason about human behavior. Enguehard, Devillers, and Hoeber (2011) calculate the fractal dimensions of ship trajectories in the Atlantic Ocean in order to infer similar fishing activities.

In addition to the above-mentioned comparison measures, Vlachos, Gunopulos, and Das (2004) propose a quantitative distance measure to assess the similarity of spatial shapes. First, the authors map each position difference vector of a path to a rotation-invariant space, where one dimension represents the direction and the other the length of the vector. In this space, Dynamic Time Warping (DTW) (see section ‘Spatiotemporal trajectory’) is applied to find shapes of similar form. This measure is not affected by rotation, scaling, and transformation. Vlachos, Gunopulos, and Das (2004) use their approach to find similar letters in handwriting trajectories.

A slightly different approach is presented by Yanagisawa, Akahani, and Satoh (2003). They interpret the paths of two moving objects as a series of consecutive position difference vectors independent of an absolute reference point in space. Then they calculate the squared Euclidean distance between these, and consequently, determine the shape similarity of the two movements. Yanagisawa, Akahani, and Satoh (2003) test their measure on simulated trajectory data.

Spatiotemporal similarity measures

Spatiotemporal position

The topological relations of two spatiotemporal positions can be inferred from those of time instance and spatial position. Two spatiotemporal positions either intersect or do not intersect. Calabrese et al. (2010) analyze sport events and mobility in cell phone networks in the city of Boston. During an event, such as a baseball game, many mobile phone users are found in the same mobile phone cell at the same time. Hence, their spatiotemporal positions intersect.

In order to compare two spatiotemporal positions quantitatively, three types of measures may be applied: purely spatial measures (e.g. Euclidean distance), purely temporal measures (e.g. temporal distance) and spatiotemporal measures (e.g. Euclidean distance and temporal distance). Spatial measures, on the one hand, compare spatiotemporal positions only with respect to space and neglect time. Hence, all quantitative measures for comparing spatial positions apply. Temporal measures, on the other hand, consider time, but neglect space. Therefore, the quantitative measures for comparing time instances apply. Spatiotemporal measures consider both, distance in time and space. Neglecting either space or time does not mean that they do not matter for analysis; rather the opposite is true. Time can only be neglected, if the two objects under comparisons exist at the same time. Consequently, space can be neglected, if the two objects attain the same spatial positions. Imagine we compare the spatiotemporal positions of stopover sites during bird migration. If two birds make a stopover at the same time, a simple spatial distance function suffices to assess the spatiotemporal similarity of the stopover sites. If the two stopover sites spatially intersect, temporal distance expresses the similarity between these.

For practical applications, spatial measures between spatiotemporal positions (and also trajectories) are most important. One example of these is the k-nearest neighbor search. In general, a nearest neighbor (NN) algorithm finds the one object in a set of query objects that is closest to a reference object. This object is denoted the NN. In the field of movement analysis, NN search is widely used to find the nearest static neighbors of a moving reference object, e.g. the nearest gas station from a car in a road network (Song and Roussopoulos 2001), or the nearest moving neighbor from a static reference object, e.g. the closest taxi unit from a costumer’s location. Frentzos et al. (2007) also propose a methodology for finding the nearest moving neighbor of a moving reference object, e.g. the nearest moving conspecific of a foraging animal.

In addition to spatial distance, we can relate two spatiotemporal positions with respect to spatial direction. Double cross calculus (Freksa 1992) is a topological measure that uses two consecutive spatiotemporal positions of a moving object A to partition space into 15 qualitative regions. The resulting double cross then describes the current location of a second moving object B relative to A’s position and current movement. In Figure 5, the moving object A (orange dot) changes its position from time

Double cross calculus (based on Freksa 1992).

The qualitative trajectory calculus (QTC) (Van de Weghe 2004) is similar to the double cross calculus. It compares the current movement of object A with respect to that of object B. In its basic form QTC has four qualitative primitives (Van de Weghe, Kuijpers, et al. 2005b). The first primitive describes whether A moves away from B, toward B, or remains stable with respect to B; the second primitive whether B moves away from A, toward A, or remains stable with respect to A. The third and fourth primitives describe in which relative direction (left, right, stable) the two objects move with respect to one other. Hence, QTC converts relative direction and distance information between two objects at one specific spatiotemporal position into a qualitative measure. In contrary to traditional approaches of qualitative spatial reasoning QTC allows for formalizing dynamic changes between two objects. Van de Weghe, Cohn, et al. (2005) apply QTC to describe overtaking events between two cars, i.e. object A starts behind object B, pulls out, overtakes B and finish in front of it.

Spatiotemporal trajectory

To the best of our knowledge, in literature, there are no genuine methods that compare entire trajectories in a topological manner. However, there are some approaches that are applicable to (sub-)trajectories with certain constraints. In an extension of the 9-intersection model Kurata and Egenhofer (2006) model the relations of directed lines. Directed lines are non-intersecting line segments in two-dimensional space. They comprise a head (i.e. the end point), a tail (i.e. the star point), and a body (the interior). Thus, trajectory segments that do not intersect may be interpreted as directed lines. Kurata and Egenhofer (2006) define 68 head–body–tail relations between two directed lines. These are capable of modeling abstract movement patterns such as two moving objects splitting and meeting. In another work Kurata and Egenhofer (2007) extend this model to relations between directed lines and regions. Amongst other things these allow for describing a moving object entering, passing through or leaving a certain geographical area.

Besides head–body–tail relations, QTC (cf. section ‘Spatiotemporal trajectory’) allows for qualitative reasoning at single spatiotemporal positions along the trajectory. Other topological approaches (i.e. Gerevini and Nebel 2002; Wolter and Zakharyaschev 2000) are not sufficiently capable of handling trajectories.

In contrast to this, quantitative trajectory similarity measures are abundantly used in literature. Quantitative trajectory similarity is closely related to the problem of time-aware clustering. Time-aware clustering finds those objects that move close to one another in space and time. In literature, various terms have been coined for time-aware clustering: some authors refer to it as trajectory clustering (Buchin et al. 2008; Nanni and Pedreschi 2006), as clustering moving objects (Li, Han, and Yang 2004), identifying flocks (Benkert et al. 2008; Wachowicz et al. 2011), convoys (Jeung et al. 2008), moving clusters (Kalnis, Mamoulis, and Bakiras 2005), or swarms (Li et al. 2010). Though the different connotations of all of these terms are generally acknowledged for – i.e. some analyze entire trajectories, whereas others concentrate on sub-trajectory similarity – they are nevertheless often used interchangeably and ground on one common denominator: objects moving close in space and time.

In movement analysis, trajectories are often interpreted as a series of positions ordered in time. Hence, methods for assessing the similarity of time series are applied also for trajectories. According to Ding et al. (2008) and Saeed and Mark (2006), similarity measures for time series can be grouped into three types: lock-step measures, elastic measures, and developed based measures. Similar to path similarity, trajectory similarity measures can also apply for the entire trajectory (global measures) or sub-trajectories (local measures). These are, however, not used as the main criteria for the following classification, but mentioned where necessary.

Lock-step measures

Lock-step measures compare the ith element of one time series A to the ith element of another time series B (see also Figure 6). The most straightforward distance measure to compare two elements is Euclidean distance. Lock-step distance measures are sensitive to noise and misalignments in time, since the mapping between the elements of two time series is fixed. Nanni and Pedreschi (2006) propose a lock-step distance measure for clustering trajectories. They calculate the sum of all distances between two spatiotemporal positions of two objects matching in time. Then they divide this distance by the duration that the two objects move together. A similar approach for assessing the dissimilarity of two trajectories (DISSIM) is presented by Frentzos, Gratsias, and Theodoridis (2007). Here, the sum of all Euclidean distances equals the dissimilarity of the trajectories. In addition to that, a local trajectory similarity measure based on Euclidean distance is presented by Buchin et al. (2009).

Lock-step measure (Euclidean distance) and elastic measure (DTW).

Elastic measures

Elastic measures either do not consider all elements in the time series for comparison, or they allow a comparison between elements that do not match in time (see also Figure 6).

Dynamic time-warping (DTW) is a similarity measure between two sequences which may vary in time or speed. The sequences are ‘stretched’ or ‘compressed’ non-linearly in the time dimension to provide a better match with another time series (Berndt and Clifford 1994; Keogh and Pazzani 2000). The technique has originated in speech recognition. Here, phonemes of an input expression may differ in length and speed from the phonemes in a reference expression. DTW allows for aligning the input and reference expression in an optimal way. DTW is particularly suited to matching sequences with missing information. Little and Gu (2001) apply DTW to trajectories from video sequences. Fu et al. (2008) combine DTW and uniform scaling to a Scaled Warped Matching technique (SWM). Uniform scaling stretches a time series in a uniform manner. Amongst others the researchers use SWM to assess the similarities of trajectories of high jumpers. In general, DTW is performed in quadratic time.

The LCSS (Vlachos, Kollios, and Gunopulos 2002) finds the longest subsequence (cf. Bollobás et al. 1997) that is common in two trajectories

Time steps is a distance measure for trajectories similar to k-points for paths (described in section ‘Spatial path and line’). In contrast to k-points a specific temporal distance lies between each two checkpoints. Time steps is computationally fast; the temporal distance defines the computational costs. Rinzivillo, Pedreschi, et al. (2008) apply time steps to cluster vehicle GPS data.

The common route and dynamics distance stems from the common route distance described in section ‘Spatial path and line’. The function regards two positions to match if they are spatially close and attained at similar relative times. Relative time starts at the time instance that marks the beginning of each trajectory. Hence, common route and dynamics analyzes whether the trajectories are spatially similar and travelled in a similar dynamic progression. Andrienko, Andrienko, and Wrobel (2007) use common route and dynamics to cluster vehicle GPS data.

Another similarity measure between two trajectories is the Fréchet distance. An intuitive definition of the Fréchet distance is presented by Aronov et al. (2006). A person and his dog move next to each other, the person keeps the dog on the leash. Both person and dog are free to choose their spatial path and their leash. The Fréchet distance denotes the minimum length of the leash that ensures that the person and the dog are always connected. Fréchet distance is computationally expensive. It is applied by Buchin, Buchin, and Gudmundsson (2010) to globally cluster bicycle GPS data and simulated random walk data and by Buchin et al. (2008) to locally cluster pedestrian GPS data.

Developed based similarity measures

Developed based similarity follows the edit distance concept, initially proposed by Levenshtein (1966). Edit distance counts the number of operations required to transform one string A into another string B. The lower this number is, the more similar the strings are. Chen, Tamer Özsu, and Oria (2005) propose a distance measure for trajectory similarity search based on edit distance called edit distance on real sequences (EDR). Given two trajectories

Other examples for developed based distances are Hamming distance (Hamming 1950) or Jaro–Winkler distance (Winkler 1999). These have, however, not been applied to trajectory data.

In addition to the above-mentioned methods, others have been developed to compare time series (Keogh and Kasetty 2003). These methods include the Sequence Weighted Alignment model (Swale) (Morse and Patel 2007), Spatial Assembling Distance (SpADe) (Chen et al. 2007), and similarity search based on Threshold Queries (TQuEST) (Aßfalg et al. 2006). It has, however, not been tested if these methods are applicable to trajectories.

Other distances measures

In addition to measures that explicitly assume trajectories as time series, there are such that ground on other concepts. These are listed here.

Lifeline distance (Sinha and Mark 2005) assumes that objects remain static for a sufficiently long time and then abruptly change their location, such as a person moving from one mobile phone cell to another. Lifeline distance represents the temporally weighted average of successive distances between the two entities. Hence, lifeline distance is not an appropriate similarity measure for moving objects that continuously change their position. Moreover, it is not a metric.

Porikli and Haga (2004) propose a distance function between two trajectories based on the Hidden Markov model (HMM). The positions along a trajectory are used as observations from which the HMM is inferred. The HMM is the previously hidden sequence of states of the object. Then the likelihood of the trajectory to its own HMM is compared to the likelihood to fit the HMM of another trajectory. This difference constitutes the HMM distance between the two trajectories. The authors use HMM to find outliers in video data of vehicle trajectories. Apart from spatiotemporal positions, HMM distance may also fall back on speed, acceleration and other qualitative observations of movement (color, size of the object) to infer current and future HMM states. HMM distance is computationally expensive, i.e. it is performed in polynomial time.

Pelekis et al. (2007) extend the LIP distance for comparing spatial paths to a spatiotemporal LIP distance (STLIP). STLIP allows for comparing two trajectories in quasilinear time. The authors apply their measure to cluster GPS vehicle data.

Velocity and acceleration

For comparing the qualitative (topological) relations of speed and acceleration (scalar) the following relational operators are used: ‘=’ (same speed/acceleration), ‘<’ (slower/lower acceleration), and ‘>’ (faster/higher acceleration). An extension of QTC (see section ‘Spatiotemporal position’) incorporates these (Van de Weghe 2004); it allows for defining whether object A moves faster, slower, or at the same speed compared to object B and whether object A accelerates faster, slower, or equally. The difference in speed/acceleration is the respective quantitative measure.

Pelekis et al. (2007) develop a speed-pattern based similarity measure. They interpret two movements as speed curves over time (or space) and calculate the similarity between these as an average of all respective differences in speed in quasilinear time. The authors apply their approach to cluster GPS trajectories of vehicles.

In general, the comparison of the dynamics of movement plays a crucial role for mode detection (Zheng, Li, et al. 2008, Zheng, Liu, et al. 2008). Zheng et al. (2010) compare speed and acceleration along multimodal GPS tracks to typical walking speed and acceleration. Thus, they partition the track into (probable) walking segments and non-walking segments. From these, further modes of transport are inferred.

Dodge, Laube, and Weibel (2012) present a different approach for comparing the dynamic similarity of movement. Their normalized weighted edit distance (NWED) translates speed and acceleration information along the movement into a sequence of different symbolic representation. One such representation may, for example, correspond to a slow speed without acceleration, another one to high and fluctuating speed. Then, edit distance is applied to these symbolic sequences, in order to find movement that has a similar dynamic behavior. Dodge, Laube, and Weibel (2012) utilize NWED to find similar instances in hurricane data and vehicle GPS data. NWED allows comparing two movement trajectories in quadratic time.

The above-mentioned relational operators also apply for comparing change of heading, if it is transferred into an angular measure. Then this parameter is mostly termed turning angle; its relations are given by ‘=’ (same turning angle), ‘<’ (smaller turning angle), ‘>’ (bigger turning angle). The difference in turning angle represents the respective quantitative measure.

Turning angle is an important parameter in the analysis of animal movement. It is closely related to shape measures (such as the sinuosity of a path) and therefore also allows for inferring the behavior of the animal under study. Waddington (1979) analyzes the turning angle of a bee’s flight to reason about different foraging behavior. Müller and Wehner (1988) study the foraging movement of ants. They find that ants move from the anthill to their foraging grounds with bigger turning angles, compared to their homebound trajectories, and follow that their homebound movement is much more determined.

Summary and conclusion

In this paper we collect measures that asses the similarity of movement. We first decompose movement into its physical quantities in time, space, and space–time. For each of these, we review primary and derived similarity measures. We show the main purpose of each measure and its computational complexity and find empirical research in the field of geographic information science and beyond where the measure is applied. Table 1 synthesizes the results and shows the reviewed similarity measures, their characteristics, and movement parameters they relate to.

Table 1.

Movement similarity measures and their characteristics.

In the review we identify a lack of topological measures for comparing (entire) spatiotemporal trajectories. To the best of our knowledge these have not been proposed or discussed in literature. Possible reasons for this are further discussed in section ‘Discussion and future work’. The opposite holds true for quantitative trajectory similarity. These are exhaustively discussed in literature.

Discussion and future work

In this paper we structure movement similarity measures according to the movement parameter they compare. Some similarity measures may, however, not be fully assigned to a single parameter. An example for such is the dynamics aware similarity method of trajectories (Trajcevski et al. 2007). This measure assesses the shape similarity of two trajectories, together with speed similarity. Hence, it would most suitably qualify as a measure for comparing spatiotemporal shape, which we do not define as a movement parameter.

Other similarity measures are capable of comparing more than one parameter. Especially, quantitative methods for spatial paths and spatiotemporal trajectories are often used interchangeably. To name two examples, LCSS and EDR can compare spatial paths and spatiotemporal trajectories. We believe that this stems from the interchangeable use of the expressions path and trajectory, on the one hand, and the fact that time is most naturally used to order respective positions along a path, on the other hand. For example, time steps analyzes path similarity irrespective of time, but requires time stamps to define which elements of the paths are to be compared.

Another clearly hybrid similarity measure is common route and dynamics distance. It does not require two objects to have similar trajectories, but they need to travel their paths in a similar temporal progression, successive spatial positions have to be reached at similar relative times.

In spite of these shortcomings, we still believe that our classification allows for a structured overview on different aspects of movement similarity, and a better understanding on how movement similarity is interpreted and implemented in geographic movement analysis.

A topic that has only been discussed briefly in this paper is that of the possible application fields for topological similarity of movement and the question: when does topological comparison of movement actually make sense? Time intervals, paths, and trajectories can only share the same positions in a reference system, if this reference system realistically allows for that, i.e. by consisting of discrete time bins, spatial cells, or a spatiotemporal derivative of both. Hence, it seems quite logical that our review reveals a lack of measures for assessing the topological relations of two spatiotemporal trajectories. We argue that such a measure may still be relevant. Furthermore, we believe that it may be derived in a straightforward manner from Egenhofer’s 9-intersection model for paths together with a simple temporal extension. The temporal extension specifies which ‘position in time’ the respective intersecting elements of the matrix have.

Figure 7 shows one example for a possible qualitative trajectory measure. In (a) the temporal extension

Topological relation for two converting and dispersing trajectories.

Last but not least we observe that certain primary similarity measures result in a similarity of derived measures. If two time intervals intersect, they have the same duration; similarity of spatial path results in a similar travelled distance and shape; trajectory similarity means similar speed and acceleration, to name but a few obvious similarity dependencies. A systematic analysis of all dependencies between different similarity measures is out of the scope of this paper, but is an interesting topic for future work.

Acknowledgments

This research is funded by the Austrian Science Fund (FWF) through the Doctoral College GIScience at the University of Salzburg (DK W 1237-N23). The research leading to these results received funding from the EU’s 7th Framework Programme (grant agreement no. 238710). The research has been carried out in the MC; IMPULSE project: https://mcimpulse.isy.liu.se.

Note

References

• Allen J. Maintaining Knowledge about Temporal Intervals. Communications of the ACM. 1983;26(11):832–843. doi: 10.1145/182.358434. [CrossRef] [Google Scholar]
• Andrienko G., Andrienko N. A General Framework for Using Aggregation in Visual Exploration of Movement Data. The Cartographic Journal. 2010;47(1):22–40. doi: 10.1179/000870409X12525737905042. [CrossRef] [Google Scholar]
• Andrienko G.2011IEEE Conference of Visual Analytics Science and Technology (VAST) [Google Scholar]
• Andrienko N., Andrienko G., Barrett L., Dostie M., Henzi P. Space Transformation for Understanding Group Movement. IEEE Transactions on Visualization and Computer Graphics. 2013;19(12):2169–2178. doi: 10.1109/TVCG.2013.193. [PubMed] [CrossRef] [Google Scholar]
• Andrienko N. Basic Concepts of Movement Data. In: Giannotti F., Pedreschi D., editors. Mobility, Data Mining, and Privacy: Geographic Knowledge Discovery. Berlin: Springer; 2008. pp. 15–38. [Google Scholar]
• Andrienko G., Andrienko N., Wrobel S. Visual Analytics Tools for Analysis of Movement Data. ACM SIGKDD Explorations Newsletter. 2007;9(2):38–46. doi: 10.1145/1345448.1345455. [CrossRef] [Google Scholar]
• Aronov B. Algorithms–ESA 2006. Berlin: Springer; 2006. Fréchet Distance for Curves, Revisited; pp. 52–63. [Google Scholar]
• Aßfalg J. Advances in Database Technology-EDBT 2006. Berlin: Springer; 2006. Similarity Search on Time Series Based on Threshold Queries; pp. 276–294. [Google Scholar]
• Bar-Shalom Y., Li X. R., Kirubarajan T. Estimation with Applications to Tracking and Navigation: Theory Algorithms and Software. John Wiley & Sons; 2004. [Google Scholar]
• Bashir F. I., Khokhar A. A., Schonfeld D.2003International Conference on Image Processing, 2003, ICIP 2003, Proceedingshttp://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1246757
• Benhamou S. How to Reliably Estimate the Tortuosity of an Animal’s Path. Journal of Theoretical Biology. 2004;229(2):209–220. doi: 10.1016/j.jtbi.2004.03.016. [PubMed] [CrossRef] [Google Scholar]
• Benkert M., Gudmundsson J., Hübner F., Wolle T. Reporting Flock Patterns. Computational Geometry: Theory and Applications. 2008;41(3):111–125. doi: 10.1016/j.comgeo.2007.10.003. [CrossRef] [Google Scholar]
• Berndt D., Clifford J.1994Using Dynamic Time Warping to Find Patterns in Time Series [Google Scholar]
• Bollobás B.1997Proceedingsof the Thirteenth Annual Symposium on Computational Geometry [Google Scholar]
• Buchin K., Buchin M., Gudmundsson J. Constrained Free Space Diagrams: A Tool for Trajectory Analysis. International Journal of Geographical Information Science. 2010;24(7):1101–1125. doi: 10.1080/13658810903569598. [CrossRef] [Google Scholar]
• Buchin K.200819th International Symposium on Algorithms and Computation [Google Scholar]
• Buchin K.2009Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems [Google Scholar]
• Buchin M. Segmenting Trajectories: A Framework and Algorithms Using Spatiotemporal Criteria. Journal of Spatial Information Science. 2011;3:33–63. [Google Scholar]
• Buchin M., Kruckenberg H., Kölzsch A. Advances in Spatial Data Handling. Berlin: Springer; 2013. Segmenting Trajectories by Movement States; pp. 15–25. [Google Scholar]
• Cai Y., Ng R.2004Proceedingsof the ACM SIGMOD International Conference on Management of Data [Google Scholar]
• Calabrese F., Colonna M., Lovisolo P., Parata D., Ratti C. Real-Time Urban Monitoring Using Cell Phones: A Case Study in Rome. IEEE Transactions on Intelligent Transportation Systems. 2011;12(1):141–151. doi: 10.1109/TITS.2010.2074196. [CrossRef] [Google Scholar]
• Calabrese F. Pervasive Computing. Berlin: Springer; 2010. The Geography of Taste: Analyzing Cell-Phone Mobility and Social Events; pp. 22–37. [Google Scholar]
• Chang K. T. Introduction to Geographic Information Systems. New Delhi: Tata McGraw-Hill; 2008. [Google Scholar]
• Chaudhuri B. B., Rosenfeld A. On a Metric Distance between Fuzzy Sets. Pattern Recognition Letters. 1996;17(11):1157–1160. doi: 10.1016/0167-8655(96)00077-3. [CrossRef] [Google Scholar]
• Chen J., Leung M. K., Gao Y. Noisy Logo Recognition Using Line Segment Hausdorff Distance. Pattern Recognition. 2003;36(4):943–955. doi: 10.1016/S0031-3203(02)00128-0. [CrossRef] [Google Scholar]
• Chen L., Tamer Özsu M., Oria V.2005Proceedings of the ACM SIGMOD International Conference on Management of Data [Google Scholar]
• Chen Y.2007IEEE 23rd International Conference on Data Engineering, 2007, ICDE 2007, Istanbul [Google Scholar]
• Chevallier D., Maho Y. Le, Brossault P., Baillon F., Massemin S. The Use of Stopover Sites by Black Storks (Ciconia nigra) Migrating between West Europe and West Africa as Revealed by Satellite Telemetry. Journal of Ornithology. 2011;152(1):1–13. doi: 10.1007/s10336-010-0536-6. [CrossRef] [Google Scholar]
• Chew L. P., Goodrich M. T., Huttenlocher D. P., Kedem K., Kleinberg J. M., Kravets D. Geometric Pattern Matching under Euclidean Motion. Computational Geometry. 1997;7(1–2):113–124. doi: 10.1016/0925-7721(95)00047-X. [CrossRef] [Google Scholar]
• Ding H. Querying and Mining of Time Series Data: Experimental Comparison of Representations and Distance Measures. Proceedings of the VLDB Endowment. 2008;1(2):1542–1552. [Google Scholar]
• Dodge S. 2011. [Google Scholar]
• Dodge S., Laube P., Weibel R. Movement Similarity Assessment Using Symbolic Representation of Trajectories. International Journal of Geographical Information Science. 2012;26(9):1563–1588. doi: 10.1080/13658816.2011.630003. [CrossRef] [Google Scholar]
• Dodge S., Weibel R., Lautenschütz A.-K. Towards a Taxonomy of Movement Patterns. Information Visualization. 2008;7(3–4):13. [Google Scholar]
• Edwards A., Phillips R. A., Watkins N. W., Freeman M. P., Murphy E. J., Afanasyev V., Buldyrev S. V. Revisiting Lévy Flight Search Patterns of Wandering Albatrosses, Bumblebees and Deer. Nature. 2007;449(7165):1044–1048. doi: 10.1038/nature06199. [PubMed] [CrossRef] [Google Scholar]
• Egenhofer M. J., Herring J. R. Categorizing Binary Topological Relations between Regions, Lines, and Points in Geographic Databases. Orono: University of Maine; 1991. [Google Scholar]
• Enguehard R., Devillers R., Hoeber O. 2011. [Google Scholar]
• Focardi S., Marcellini P., Montanaro P. Do Ungulates Exhibit a food density threshold? A field study of Optimal Foraging and Movement Patterns. The Journal of Animal Ecology. 1996:606–620. doi: 10.2307/5740. [CrossRef] [Google Scholar]
• Fox A. D., Glahder C. M., Walsh A. J. Spring Migration Routes and Timing of Greenland White-Fronted Geese – Results from Satellite Telemetry. Oikos. 2003;103(2):415–425. doi: 10.1034/j.1600-0706.2003.12114.x. [CrossRef] [Google Scholar]
• Frank A. U. Qualitative Spatial Reasoning: Cardinal Directions as an Example. International Journal of Geographical Information Science. 1996;10(3):269–290. [Google Scholar]
• Freksa C.1992Theories and Methodsof Spatio-Temporal Reasoning in Geographic Space [Google Scholar]
• Frentzos E., Gratsias K., Pelekis N., Theodoridis Y. Algorithms for Nearest Neighbor Search on Moving Object Trajectories. Geoinformatica. 2007;11(2):159–193. doi: 10.1007/s10707-006-0007-7. [CrossRef] [Google Scholar]
• Frentzos E., Gratsias K., Theodoridis Y.2007Data Engineering, 2007, ICDE 2007, IEEE 23rd International Conference on, 2007 [Google Scholar]
• Frentzos E. Trajectory Database Systems. In: Giannotti F., Pedreschi D., editors. Mobility, Data Mining, and Privacy: Geographic Knowledge Discovery. Berlin: Springer; 2008. pp. 151–187. [Google Scholar]
• Fu A. W.-C., Keogh E., Lau L. Y. H., Ratanamahatana C. A., Wong R. C. Scaling and Time Warping in Time Series Querying. The VLDB Journal—The International Journal on Very Large Data Bases. 2008;17(4):899–921. doi: 10.1007/s00778-006-0040-z. [CrossRef] [Google Scholar]
• Furletti B., P Cintia, C. Renso, L. Spinsanti.2013Proceedings of the 2nd ACM SIGKDD InternationalWorkshop on Urban Computing [Google Scholar]
• Gavric K.201110th International Conference on Telecommunication in Modern Satellite Cable and Broadcasting Services (TELSIKS) [Google Scholar]
• Gerevini A., Nebel B.2002ECAIAmsterdam: IOS Press [Google Scholar]
• Girardin F., Calabrese F., Fiore F. D., Ratti C., Blat J. Digital Footprinting: Uncovering Tourists with User-Generated Content. IEEE Pervasive Computing. 2008;7(4):36–43. doi: 10.1109/MPRV.2008.71. [CrossRef] [Google Scholar]
• Golumbic M. C., Shamir R.1993Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach Journal of the ACM (JACM )4051108–1133. 10.1145/174147.169675 [CrossRef] [Google Scholar]
• González M. C., Hidalgo C. A., Barabási A.-L. Understanding Individual Human Mobility Patterns. Nature. 2008;453(7196):779–782. doi: 10.1038/nature06958. [PubMed] [CrossRef] [Google Scholar]
• Gruteser M., Hoh B. Security in Pervasive Computing. Berlin: Springer; 2005. On the Anonymity of Periodic Location Samples; pp. 179–192. [Google Scholar]
• Gudmundsson J., van Kreveld M.2006Proceedings of the 14th Annual ACM International Symposium on Advances in Geographic Information Systems [Google Scholar]
• Güting R. H., Schneider M. Moving Objects Databases. San Francisco: Morgan Kaufmann; 2005. [Google Scholar]
• Hamming R. W. Error Detecting and Error Correcting Codes. Bell System Technical Journal. 1950;29(2):147–160. doi: 10.1002/j.1538-7305.1950.tb00463.x. [CrossRef] [Google Scholar]
• Higuchi H., Ozaki K., Fujita G. O., Minton J., Ueta M., Soma M., Mita N. Satellite Tracking of White-naped Crane Migration and the Importance of the Korean Demilitarized Zone. Conservation Biology. 1996;10(3):806–812. doi: 10.1046/j.1523-1739.1996.10030806.x. [CrossRef] [Google Scholar]
• Hodgson S., Quinn T. P., Hilborn R., Francis R. C., Rogers D. E. Marine and Freshwater Climatic Factors Affecting Interannual Variation in the Timing of Return Migration to Fresh Water of Sockeye Salmon (Oncorhynchus nerka) Fisheries Oceanography. 2006;15(1):1–24. doi: 10.1111/j.1365-2419.2005.00354.x. [CrossRef] [Google Scholar]
• Hofmann-Wellenhof B., Legat K., Wieser M. Navigation: Principles of Positioning and Guidance. Wien: Springer Verlag; 2003. [Google Scholar]
• Jeung H., Yiu M. L., Jensen C. Trajectory Pattern Mining. In: Zheng Y., Zhou X., editors. Computing with Spatial Trajectories. New York: Springer; 2011. pp. 143–177. [Google Scholar]
• Jeung H. Discovery of Convoys in Trajectory Databases. Proceedings of the VLDB Endowment. 2008;1(1):1068–1080. [Google Scholar]
• Junejo I., Javed O., Shah M.2004Proceedings of the 17th International Conference on Pattern Recognition [Google Scholar]
• Kalnis P., Mamoulis N., Bakiras S. Advances in Spatial and Temporal Databases. Berlin: Springer; 2005. On Discovering Moving Clusters in Spatio-Temporal Data; pp. 364–381. [Google Scholar]
• Kang C.201018th International Conference on Geoinformatics [Google Scholar]
• Keogh E., Kasetty S. On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration. Data Mining and Knowledge Discovery. 2003;7(4):349–371. doi: 10.1023/A:1024988512476. [CrossRef] [Google Scholar]
• Keogh E., Pazzani M.2000Proceedings of theSixth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining [Google Scholar]
• Kjellén N. Differential Timing of Autumn Migration between Sex and Age Groups in Raptors at Falsterbo, Sweden. Ornis Scandinavica. 1992;23:420–434. doi: 10.2307/3676673. [CrossRef] [Google Scholar]
• Koch W. On Bayesian Tracking and Data Fusion: A Tutorial Introduction with Examples. IEEE Aerospace and Electronic Systems Magazine. 2010;25(7):29–52. doi: 10.1109/MAES.2010.5546307. [CrossRef] [Google Scholar]
• Kovach R. P., Joyce J. E., Echave J. D., Lindberg M. S., Tallmon D. A., Carlson S. M. Earlier Migration Timing, Decreasing Phenotypic Variation, and Biocomplexity in Multiple Salmonid Species. PloS one. 2013;8(1):e53807. doi: 10.1371/journal.pone.0053807. [PMC free article] [PubMed] [CrossRef] [Google Scholar]
• Kraak M.-J. 2003. pp. 10–16. [Google Scholar]
• Kurata Y., Egenhofer M. J. The Head-Body-Tail Intersection for Spatial Relations between Directed Line Segments. In: Raubal M., Miller H., Frank A., Goodchild M., editors. Geographic Information Science. Lecture Notes in Computer Science; Berlin Heidelberg: Springer: 2006. pp. 269–286. [Google Scholar]
• Kurata Y., Egenhofer M. J.2007BMI [Google Scholar]
• Laube P., Dennis T., Forer P., Walker M. Movement beyond the Snapshot–Dynamic Analysis of Geospatial Lifelines. Computers, Environment and Urban Systems. 2007;31(5):481–501. doi: 10.1016/j.compenvurbsys.2007.08.002. [CrossRef] [Google Scholar]
• Laube P., Imfeld S. Analyzing Relative Motion within Groups Oftrackable Moving Point Objects. Geographic Information Science. 2002:132–144. doi: 10.1007/3-540-45799-2_10. [CrossRef] [Google Scholar]
• Laube P., Imfeld S., Weibel R. Discovering Relative Motion Patterns in Groups of Moving Point Objects. International Journal of Geographical Information Science. 2005;19(6):639–668. doi: 10.1080/13658810500105572. [CrossRef] [Google Scholar]
• Lee J.-G., Han J., Whang K.-Y.2007Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data [Google Scholar]
• Levenshtein V. I. Binary Codes Capable of Correcting Deletions, Insertions, and Reversals. Soviet Physics Doklady. 1966;10(8):707–710. [Google Scholar]
• Lewandowski W., Thomas C. GPS Time Transfer. Proceedings of the IEEE. 1991;79(7):991–1000. doi: 10.1109/5.84976. [CrossRef] [Google Scholar]
• Li Z. Swarm: Mining Relaxed Temporal Moving Object Clusters. Proceedings of the VLDB Endowment. 2010;3(1–2):723–734. [Google Scholar]
• Li Y., Han J., Yang J.2004Proceedings of the Tenth ACMSIGKDD International Conference on Knowledge Discovery and Data Mining [Google Scholar]
• Liao L., Patterson D. J., Fox D., Kautz H. Building Personal Maps from GPS Data. Annals of the New York Academy of Sciences. 2006;1093(1):249–265. doi: 10.1196/annals.1382.017. [PubMed] [CrossRef] [Google Scholar]
• Lin B., Su J.2005Proceedings of the 13th AnnualACM International Workshop on Geographic Information Systems [Google Scholar]
• Lin C., Chang P., Luh J. Formulation and Optimization of Cubic Polynomial Joint Trajectories for Industrial Robots. IEEE Transactions on Automatic Control. 1983;28(12):1066–1074. doi: 10.1109/TAC.1983.1103181. [CrossRef] [Google Scholar]
• Lin D.1998ICML [Google Scholar]
• Little J., Gu Z.2001SPIE Storage and Retrieval for Media Databases [Google Scholar]
• Long J. A., Nelson T. A.2012International Journal of Geographical Information Science 10.1080/13658816.2012.682578 [CrossRef] [Google Scholar]
• Longley P., M. F. Goodchild, D. Maguire, D. Rhind. Geographic Information Systems and Science. Chichester: John Wiley & Sons; 2005. [Google Scholar]
• Luisi P. L. The Interplay of Cyclic and Linear Time in the Biological World. Annals of the New York Academy of Sciences. 1999;879(1):98–109. doi: 10.1111/j.1749-6632.1999.tb10408.x. [CrossRef] [Google Scholar]
• Macedo J. Trajectory Data Models. In: Giannotti F., Pedreschi D., editors. Mobility, Data Mining, and Privacy: Geographic Knowledge Discovery. Berlin: Springer; 2008. pp. 123–150. [Google Scholar]
• Mandelbrot B. B. How Long is the Coast of Britain? Statistical Self-Similarity and Fractional Dimension. Science. 1967;156(3775):636–638. doi: 10.1126/science.156.3775.636. [PubMed] [CrossRef] [Google Scholar]
• Mandelbrot B. B. The Fractal Geometry of Nature/Revised and Enlarged Edition. New York: WH Freeman and Co; 1983. p. 1. [Google Scholar]
• Mark D. M., Egenhofer M. J. 1998. [Google Scholar]
• Mate B. R., Nieukirk S. L., Kraus S. D. Satellite-Monitored Movements of the Northern Right Whale. The Journal of Wildlife Management. 1997:1393–1405. doi: 10.2307/3802143. [CrossRef] [Google Scholar]
• Melnychuk M. C., Welch D. W., Walters C. J. Spatio-Temporal Migration Patterns of Pacific Salmon Smolts in Rivers and Coastal Marine Waters. PloS one. 2010;5(9):e12916. doi: 10.1371/journal.pone.0012916. [PMC free article] [PubMed] [CrossRef] [Google Scholar]
• Merrick R. L., Loughlin T. R. Foraging Behavior of Adult Female and Young-of-the-Year Steller Sea Lions in Alaskan Waters. Canadian Journal of Zoology. 1997;75(5):776–786. doi: 10.1139/z97-099. [CrossRef] [Google Scholar]
• Minett C. F., A. M. Salomons, W. Daamen, B. Van Arem, S. Kuijpers.2011IEEE Forum on Integrated and Sustainable Transportation System (FISTS) [Google Scholar]
• Morse M. D., Patel J. M.2007Proceedingsof the 2007 ACM SIGMOD International Conference on Management of Data [Google Scholar]
• Müller M., Wehner R. Path Integration in Desert Ants, Cataglyphis Fortis. Proceedings of the National Academy of Sciences. 1988;85(14):5287–5290. doi: 10.1073/pnas.85.14.5287. [PMC free article] [PubMed] [CrossRef] [Google Scholar]
• Nanni M., Pedreschi D. Time-Focused Clustering of Trajectories of Moving Objects. Journal of Intelligent Information Systems. 2006;27(3):267–289. doi: 10.1007/s10844-006-9953-7. [CrossRef] [Google Scholar]
• Parent C., Pelekis N., Theodoridis Y., Yan Z., Spaccapietra S., Renso C., Andrienko G. Semantic Trajectories Modeling and Analysis. ACM Computing Surveys. 2013;45(4):1–32. doi: 10.1145/2501654.2501656. [CrossRef] [Google Scholar]
• Pauly A., Schneider M.2004Advances in Databasesand Information SystemsA. Benczúr, J. Demetrovics, G. Gottlob. [Google Scholar]
• Pelekis N., Andrienko G., Andrienko N., Kopanakis I., Marketos G., Theodoridis Y. Visually Exploring Movement Data via Similarity-Based Analysis. Journal of Intelligent Information Systems. 2012;38(2):343–391. doi: 10.1007/s10844-011-0159-2. [CrossRef] [Google Scholar]
• Pelekis N.200714th International Symposium on Temporal Representation and Reasoning [Google Scholar]
• Perlibakas V. Distance Measures for PCA-Based Face Recognition. Pattern Recognition Letters. 2004;25(6):711–724. doi: 10.1016/j.patrec.2004.01.011. [CrossRef] [Google Scholar]
• Pfoser D., Jensen C.1999Advances inSpatial Databases [Google Scholar]
• Porikli F., Haga T.2004CVPRW’04 Conference on Computer Vision and Pattern Recognition WorkshopWashington, DC: IEEE [Google Scholar]
• Price L. R.2013The Oxford Handbook of Quantitative Methods in PsychologyT. D. Little.2Oxford: Oxford University Press [Google Scholar]
• Ranacher P., Rousell A. 2013. [Google Scholar]
• Rinzivillo S. Visually Driven Analysis of Movement Data by Progressive Clustering. Information Visualization. 2008;7(3–4):225. [Google Scholar]
• Rinzivillo S. Knowledge Discovery from Geographical Data. In: Giannotti F., Pedreschi D., editors. Mobility, Data Mining, and Privacy: Geographic Knowledge Discovery. Berlin: Springer; 2008. pp. 243–296. [Google Scholar]
• Sadilek A., Kautz H. A. 2010. [Google Scholar]
• Saeed M., Mark R.2006AMIA Annual Symposium Proceedings, [Google Scholar]
• Schiffer S., Ferrein A., Lakemeyer G.2006Qualitative Constraint Calculi, Workshop at KI [Google Scholar]
• Scivos A., Nebel B. Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation. Spatial Information Theory. 2001;2205/2001:431–446. doi: 10.1007/3-540-45424-1_29. [CrossRef] [Google Scholar]
• Sinha G., Mark D. M. Measuring Similarity between Geospatial Lifelines in Studies of Environmental Health. Journal of Geographical Systems. 2005;7(1):115–136. doi: 10.1007/s10109-005-0153-8. [CrossRef] [Google Scholar]
• Song Z., Roussopoulos N. Advances in Spatial and Temporal Databases. Berlin: Springer; 2001. K-Nearest Neighbor Search for Moving Query Point; pp. 79–96. [Google Scholar]
• Spaccapietra S., Parent C., Damiani M. L., de Macedo J. A., Porto F., Vangenot C. A Conceptual View on Trajectories. Data & Knowledge Engineering. 2008;65(1):126–146. doi: 10.1016/j.datak.2007.10.008. [CrossRef] [Google Scholar]
• Tøttrup A. P.2012Proceedings of the Royal Society B: Biological Sciences [Google Scholar]
• Trajcevski G., H. Ding, P. Scheuermann, R. Tamassia, D. Vaccaro.2007Proceedings of the 15th AnnualACM International Symposium on Advances in Geographic Information Systems [Google Scholar]
• Tzavella K., Ulmke M. GI_Forum 2013. Salzburg: 2013. Updating Road Maps Using Particle Filter Tracking and Geographic Information. [Google Scholar]
• Ueta M., Sato F., Nakagawa H., Mita N. Migration Routes and Differences of Migration Schedule between Adult and Young Steller’s Sea Eagles Haliaeetus Pelagicus. Ibis. 2000;142(1):35–39. doi: 10.1111/j.1474-919X.2000.tb07681.x. [CrossRef] [Google Scholar]
• Van de Weghe N. 2004. [Google Scholar]
• Van de Weghe N., Cohn A. G., Maeyer P. D., Witlox F. Representing Moving Objects in Computer-Based Expert Systems: The Overtake Event Example. Expert Systems with Applications. 2005;29(4):977–983. doi: 10.1016/j.eswa.2005.06.022. [CrossRef] [Google Scholar]
• Van de Weghe N., B. Kuijpers, P. Bogaert, P. De Maeyer. GeoSpatial Semantics. Berlin: Springer; 2005. A Qualitative Trajectory Calculus and the Composition of its Relations; pp. 60–76. [Google Scholar]
• Venema Y. Temporal Logic. In: Goble L., editor. The Blackwell Guide to Philosophical Logic. Oxford: Blackwell Publishers; 2001. pp. 203–223. [Google Scholar]
• Versichele M., Neutens T., Delafontaine M., Van de Weghe N. The Use of Bluetooth for Analysing Spatiotemporal Dynamics of Human Movement at Mass Events: A Case Study of the Ghent Festivities. Applied Geography. 2012;32(2):208–220. doi: 10.1016/j.apgeog.2011.05.011. [CrossRef] [Google Scholar]
• Vlachos M., Gunopulos D., Das. G.2004Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining [Google Scholar]
• Vlachos M., Kollios G., Gunopulos. D.2002Data Engineering, 2002, Proceedings, 18th International Conference on, 2002 [Google Scholar]
• Wachowicz M., Ong R., Renso C., Nanni M. Finding Moving Flock Patterns among Pedestrians through Collective Coherence. International Journal of Geographical Information Science. 2011;25(11):1849–1864. doi: 10.1080/13658816.2011.561209. [CrossRef] [Google Scholar]
• Waddington K. D. Flight Patterns of Three Species of Sweat Bees (Halictidae) Foraging at Convolvulus Arvensis. Journal of the Kansas Entomological Society. 1979:751–758. [Google Scholar]
• Winkler W. E. 1999. [Google Scholar]
• Wolter F., Zakharyaschev. M. 2000. [Google Scholar]
• Yanagisawa Y., Akahani J.-I., Satoh. T.2003Mobile Data Management [Google Scholar]
• Zhang Z., Huang K., Tan. T.200618th International Conference on Pattern Recognition, ICPR 2006 [Google Scholar]
• Zheng K., G. Trajcevski, X. Zhou, P. Scheuermann, Peter.2011Proceedings of the 14th International Conference on Extending Database Technology [Google Scholar]
• Zheng Y., Chen Y., Li Q., Xie X., Ma W. Understanding Transportation Modes Based on GPS Data for Web Applications. ACM Transactions on the Web (TWEB)2010;4(1):1–36. doi: 10.1145/1658373.1658374. [CrossRef] [Google Scholar]
• Zheng Y.2008Proceedings of the 10thInternational Conference on Ubiquitous Computing, 2008 [Google Scholar]
• Zheng Y.2008Proceedings of the 17th International Conference on World Wide Web [Google Scholar]