Similarity Search Of Trajectory Data And Its Applications

Trajectory data is playing an increasingly important role in our daily lives, as well as in commercial applications and scientific research. With the rapid development of wireless communication and mobile computing techniques, the size of trajectory data that we are capable to acquire becomes unprecedented large. Such enormous amount of trajectory data not only brings huge research value, but also poses severe challenges to the management, computation and mining of such data. Due to the limited storage and computation resources, we need to study how to compress these trajectory data without hurting its utility, as well as to study how to efficiently complete some basic tasks, such as similarity search of trajectory data. This dissertation focuses on similarity search of trajectory data, and with the deficiencies of existing researches in mind, introduces trajectory compression algorithm, and effective similarity search algorithm. Based on this, it also explores how to utilize trajectory data, and exploits the magnetic sensor to design and implement an character inputting system. Specifically, this dissertation studies the following aspects.1. Similarity search of trajectories based on important segments. Existing trajectory compression algorithms only compresses each trajectory in isolation, and the compressed trajectory will lose detail semantic information. Thus, we propose a new algorithm for trajectory compression, which segmentizes each trajectory and computes the segment-wise weight, then extracts those seg-ments with highest weights to form the compressed trajectory. This way, we can retain the details of those important parts of the trajectory, and enrich the seman-tic meaning of the compressed trajectory. The experiment results demonstrate that this algorithm achieves satisfactory compression ratio without sacrificing the utility of trajectory data.2. Similarity search of trajectories based on segment rotation. As the most widely used distance measure for trajectories, Dynamic Time Warp-ing (DTW) can handle local time shift in these data, thus achieves high retrieval accuracy. However, the computation overhead of DTW is rather high. When ap-plying DTW, generally a lower bound is first computed to prune those trajectories that are impossible to be included in the result set, thus improves the retrieval ef-ficiency. Existing lower bounds for DTW do not make use of the characteristics of multi-dimensional trajectories, therefore we propose a new lower bound for DTW, which effectively improves the similarity search of multi-dimensional tra-jectories. We demonstrate its effectiveness through experiments on real world and synthetic datasets.3. Character inputting system based on magnetic sensor. As an exploration of the application of trajectory data, we design and implement a character inputting system based on magnetic sensor, which can be deployed on any smart devices that embedded with a magnetic sensor. It first eliminates the impact of users’ heterogeneous writing patterns through a trajectory transfor-mation algorithm, then it utilizes DTW as the distance measure of trajectories, and uses1nearest neighbor classification to recognize the inputted character. We carry out extensive experiments in real world scenarios, and the results demon-strate that our system can achieve recognition accuracy of94.99%.