Complex Motion Pattern Queries for Trajectories

This thesis presents several new query processing techniques, called complex motion pattern queries, specifically designed for trajectories. First, it begins with the definition of flexible pattern query, a very powerful, yet easy to use motion pattern query which allows users to select trajectories based on specific events of interest. Flexible pattern query is described as regular expressions over a spatial alphabet that can be implicitly/explicitly "anchored" to the time domain. Moreover, it allows users to include variables in the pattern query, and thus greatly increase its expressive power. Second, the Spatio-Temporal Pattern System (STPS) is presented, which is an adaptation of flexible pattern query for mobile phone-call databases. These databases contain many millions of records with information about mobile phone calls, including the user's location, when the call was made/received, and duration of the call, among other information. The design of STPS takes into consideration the layout of the areas being covered by the cellular towers, as well as areas that label places of interest (e.g. neighborhoods, parks). Third, density-based pattern query is described for discovering trajectories that follow a pattern that captures the aggregate behavior of trajectories as groups. Several evaluation algorithms are presented for finding groups of trajectories that move together, i.e. within a predefined distance to each other for a continuous period of time. The last complex motion pattern query proposed in this thesis is for diversifying query results. The goal of this query is to build a result that contains relevant elements to the user's query and diverse elements to other elements in the result. This pattern query is useful when, for example, an exploratory query to a very large database leads to a vast number of answers in the result. Navigating through such a large result requires huge effort and users give up after perusing through the first few results, thus some interesting results hidden further down the result set can easily be missed. To overcome this problem, a generic framework for diversifying query results is presented. Two new evaluation methods, as well as several existing ones, are described and tested in the proposed framework. The efficiency and effectiveness of the proposed complex motion pattern queries are demonstrated through an extensive experimental evaluation