The increasing ubiquity of Global Positioning System devices and the widespread deployment of monitoring and tracking mechanisms, including video cameras, cellular phones, activity trackers and roadside sensors are creating very large spatio-temporal datasets that are extremely rich in semantics. Such data embed a great deal of high-level information on the behavior of moving objects as well their interactions with objects in the environment and with each other. Standard queries such as range queries and joins may be adequate for extracting the semantics of spatial data, but do scant justice to the inherent richness of spatio-temporal semantics. This project will develop approaches aimed specifically at extracting semantic and behavioral information from trajectory datasets. For instance, a moving object conducting surveillance on a region will remain in the vicinity of the region for the duration of surveillance. Detecting this behavior is difficult with standard approaches: a range query would require the user to specify the spatial and temporal ranges of surveillance, when the intent is, in fact, to determine both. The proposed work has many national security applications, including law enforcement, surveillance and security monitoring as well as social and commercial applications, such as in social networks, link analysis and epidemiology. The solutions developed will increase the utility of spatio-temporal data, specifically for tasks that require investigative exploration.
This project addresses a novel class of problems in the spatio-temporal domain, which raise a novel set of technical challenges: First, it studies queries that elicit the semantics of interactions between moving objects and their environment. Second, it studies queries eliciting the semantics of interactions, such as potential meetings between moving objects themselves. Third, it explores such queries in the real-world contexts, where the available data is incomplete and imprecise. Examples of the first class of query include "dwell regions" queries, which explore spatio-temporal proximity between moving objects and objects in the environment, with applications to detection of surveillance of regions by moving objects. The project will also address "conclave" queries that illustrate the second and third challenges above. Such queries return possible meeting points between moving objects when their trajectories are not known fully or precisely. The proposed work also explores complex spatio-temporal "reachability" queries, which elicit possible interactions between objects via intermediaries. Finally, given the sheer magnitude of spatio-temporal datasets, this project aims to provide solutions that scale. A basic question is then how to efficiently index trajectory data. While there have been various past works in this domain, this project proposes a fourth challenge: can Hilbert Curves been used to index trajectories? Space filling curves (SFCs) have been shown to be advantageous in indexing spatial objects since they can reduce the space dimensionality. In past research, SFCs have been mainly used to index multidimensional points or order arbitrary objects; they have not though been directly used for indexing trajectories due to various challenges that this project aims to overcome. The project web site (www.cs.ucr.edu/~tsotras/semtraj/index.html) will provide access to the project results, including source code of the developed algorithms and relevant data.
