How to compare movement? A review of physical movement similarity measures in geographic information science and beyond.

Author:Ranacher, Peter


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 spatio-temporal 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 to the circle is at location [A.sub.0]. It moves to location [A.sub.3] where it arrives at time 13. On its way, it passes the positions [A.sub.1] and [A.sub.2]. The square starts its movement at location [B.sub.1] at time [t.sub.1]. It moves to location [B.sub.2] = [A.sub.2] where it arrives at time [t.sub.2]. Now, how similarly do the two objects move? In order to answer this question we have to first specify the term similarity.

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 [B.sub.2] = [A.sub.2]. Moreover, the two objects attend this position at the same time. Therefore, not only the paths but also the spatiotemporal trajectories of the two objects intersect. Hence, we compare movement from a spatiotemporal perspective.

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). Gifting 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...

To continue reading