Abstract
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
Key Terms in this Chapter
Spatial-Temporal Index: A spatial-temporal index is an advanced index structure where the indexing key is the location and timestamp of an object.
Global Positioning System (GPS): A satellite navigation system that provides accurate location and time information anywhere on the Earth where there is an unobstructed sight to four or more GPS satellites.
Query Predicate: A query predicate is a conditional expression that defines the filter condition in a query.
Spatial Range Query: Given a query object q , a distance threshold ? and a dataset D , a spatial range query returns a set of objects in D that is at most ? distant from the query object q .
Spatial Index: A spatial index is a specialized indexing structure where the indexing key is the spatial location of objects indexed. The type of searches on an spatial index is the set of spatial queries, for example, range and overlapping queries.
Indexing Structure: A data structure that speed the search operations on a database. Creating and Maintaining an index structure has an associated cost of extra writes and storage space. This cost is amortized at the search phase, where querying using an index is faster than searching every row in a database.
Similarity Query: Given a query object q , a dataset D , a distance threshold ?, and a similarity function that returns how similar two objects are, a similarity query returns a subset of objects from D that has at least ? similar to the query object q .
Radio-Frequency Identification (RFID): A system that uses wireless technology and two components: readers and tags. The reader device has antennas that emit radio waves and receive signals back from tag devices. Tags uses radio waves to communicate back to reader devices. Tag devices are used to automatically identify and track objects that are attached with the tags.
Join Query: Given a distance threshold ?, a similarity function that returns how similar two objects are, and two datasets D 1 and D 2 , a join query returns pair of objects from D 1 and D 2 that are at least ? similar to each other.
Spatio-Temporal Databases: a database that provides storage, management and query capabilities for spatio-temporal data.
Spatial k-Nearest Neighbor Query: Given a query object q and a dataset D , a k-nearest neighbor query returns the k closest spatial objects to query q .