With the recent advancements and wide usage of location detection devices, very large quantities of data are collected by GPS and cellular technologies in the form of trajectories. The wide and increasing availability of such collected data has led to research advances in behavioral aspects of the monitored subjects (e.g., wild animals, people, and vehicles). Using trajectory data harvested by mobile devices, trajectories can be explored using motion pattern queries based on specific events of interest. While most research works on trajectory-based queries has focused on traditional range, nearest-neighbor, and similarity and join queries, there has been an increasing need to query trajectories using complex, yet more intuitive, motion patterns. In this chapter, we describe in detail complex motion pattern queries, which allow users to focus on trajectories that follow a specific sequence of spatio-temporal events. We demonstrate how these motion pattern queries can greatly help users to get insights from very large trajectory datasets.
TopIntroduction
The wide availability of location and mobile technologies (e.g., cheap GPS devices, ubiquitous cellular networks and Radio-Frequency Identification (RFID) tags), as well as the improved location accuracy has enabled a vast amount of new applications to collect and analyze data in the form of trajectories. For example, new generations of tracking systems have emerged, providing complex services to end users (e.g., detect when a truck deviate from its route, when two moving objects are closed together, when a bus will arrive at a certain bus stop). The accuracy of the generated spatio-temporal data has also improved: instead of the traditional cell phone tower triangulation method, assisted GPS (NAVCEN, 1996) was recently introduced to improve location accuracy, such as enhanced 911 services (Consumer & Governmental Affairs Bureau, 2013).
These advances have led to the generation of very large spatio-temporal datasets in the form of trajectories. A trajectory is a time- ordered sequence of spatial locations (e.g., latitude/longitude) for a moving object id. This sequence may also have some other reading, for instance, speed, outside temperature, and textual information. Figure 1 shows an example of a trajectory Tid = {moid, (l1,t1), (l2,t2), … (l9,t9)} with 9 locations moving in the 2 dimensional space.
Figure 1. Example of a trajectory Tid with a sequence of 9 locations
Given the huge volume of data generated in the form of trajectories, there is an increasing need to develop more effective and efficient techniques for data management and query evaluation over trajectories. Past research works on querying trajectory data have mainly concentrated on traditional spatio-temporal queries. Examples of such queries are:
- 1.
Range and nearest neighbors queries, e.g., “find all trajectories that were in region q between 1pm and 3pm” (see Figure 2(a));
- 2.
Similarity-based queries, e.g., “find the 2 most similar trajectories to trajectory q according to a predefined similarity measure” (see Figure 2(b)); and
- 3.
Spatial-temporal join queries, e.g., “given two datasets S1 and S2, find all pairs of trajectories that are at most 10 miles distant from each other” (see Figure 2(c)).
Figure 2. Examples of traditional spatio-temporal queries: (a) spatio-temporal range; (b) Spatio-temporal similarity; (c) spatial-temporal join
A major problem with the above three approaches is that a range query may retrieve too many results, as exemplified in Figure 3(a). Since a spatio-temporal range query uses a single predicate to define the query condition, the returned answer may include a very large number of trajectories. On the other hand, using a similarity-based and join queries may be too restrictive and, thus, return no result, as illustrated in Figure 3(b). Since the query is defined using a whole/part of trajectory, the qualified answers have to “follow” the same pattern in space and time, which may be too restrictive.
Figure 3. Limitations of traditional spatio-temporal queries: (a) traditional spatio-temporal range query; (b) similarity and join based queries