A framework for complex trajectory query processing

The increasing popularity of the GPS technology and the growing amount of highly accurate trajectory data it generates have created the need for developing applications that efficiently store and query trajectories of moving objects. Traditional relational database management systems, however, are not well equipped to handle this novel and complex data type. The set of predicates, employed by the standard query languages is not capable of capturing the topological relationships which exist between spatial objects. Also, the temporal aspect of the trajectories poses new challenges for query evaluation. Depending on the application, trajectories are processed either in an archive or in a streaming environment. Archival storage allows for offline processing and can use specialized indexing structures for fast access. On the other hand, in spatiotemporal data streams the processing is typically done in main memory so as it can handle the high location update rates. This thesis proposes efficient methods for evaluating complex pattern and similarity queries over trajectorial data in either archival or streaming environments. Using a novel inverted indexing scheme we propose a generic framework for efficiently answering a wide range of complex trajectory queries in streaming environment, based on the incremental reevaluation paradigm. For archival data we propose a set of efficient algorithms based on threshold pruning which narrow down the search in the index space to the regions which are likely to contain a solution to the query. The effectiveness of the proposed algorithms and indexing schemes is demonstrated through a thorough experimental evaluation.