The recent years have witnessed a large number of emerging applications in location based services, thanks to the wide spread use of GPS devices, cellular phones, RFID tags and mobile sensor nodes. A fundamental technology that enables such services is the efficient management of the vast volume of spatio-temporal information for the mobile entities, which largely exists in the format of spatio-temporal trajectories. As a new data type, trajectories of moving objects have posed new challenges to efficient query processing, answer maintenance and knowledge discovery. In this dissertation, we present novel paradigms and algorithms on the efficient management of spatio-temporal trajectories. First of all, we introduce our framework on efficient maintenance of continuous queries on trajectories pertaining to the future. When a traffic abnormality happens, it may affect the answer set of some pending queries and our framework performs efficient re-evaluation in three steps to bring the answers up-to-date. We then present a novel scheme that combines routing and partial aggregation in cellular network settings for efficient query answer delivery. Our scheme exploits the processing capability of distributed database servers along the route of answer delivery for parallel partial aggregation. Secondly, we describe a novel framework on index-based similarity join of trajectories, which is an important primitive to speed up many data mining applications for spatio-temporal data. Our framework measures the trajectory similarity with a novel distance function and utilizes existing spatio-temporal indices in the native space for efficient join processing. Furthermore, we propose an adaptive filtering technique to improve the robustness of our distance measure against noise. We have also extended our framework to support similarity join of trajectories on the road network, where the distance between moving object locations is defined on the network distance. Thirdly, we develop the notion of similarity of trajectories, by taking into account the dynamics of the moving objects and allowing rigid motion transformations, in order to reason about the similarity of trajectories from different geographic regions. We present exact algorithm for finding the optimal distance of trajectories under transformation, and further propose an efficient algorithm that computes approximate answers with a tight error bound. For each of the technique or algorithm presented, we have conducted extensive experimental evaluations using realistic or real world data sets to demonstrate the validity of our approaches and their effectiveness.

Last modified

• 09/14/2018

Creator

• Hui Ding

DOI

• https://doi.org/10.21985/N27T67

Subject

• Computer Science

Keyword

• moving object database
• spatio-temporal trajectory

Date created

• 2008-09-09

Resource type

• Dissertation

Rights statement

• In Copyright