MATH Seminar
| Title: Indexing Moving Objects for Predictive Spatio-Temporal Queries |
|---|
| Defense: Dissertation |
| Speaker: Xiaofeng Xu of Emory University |
| Contact: Xiaofeng Xu, xiaofeng.xu@emory.edu |
| Date: 2016-01-28 at 2:30PM |
| Venue: W304 |
| Download Flyer |
| Abstract: The rapid development of positioning techniques has enabled information to be widely collected on continuously moving objects, such as vehicles and mobile device users. Since moving object data is large and updates frequently, database systems supporting massive updates and predictive spatio-temporal queries are essential for modern location-based services. Traditional spatial accessing or indexing mechanisms barely consider velocity information of the objects to improve query performance. In this dissertation, I present novel approaches that augment existing tree-based and grid-based indexes for moving object databases with velocity information and prove that these approaches can significantly improve query performance with comparable update performance in both in-disk and in-memory scenarios.. Predictive range query, which retrieves objects in a certain spatial region at some future time, is the most motivating type of spatio-temporal queries in real world location-based services. Different from predicting future location of a single moving object, performing predictive range queries over large moving object databases incurs much heavier computational burden, which makes efficiency as important as accuracy for real-time spatio-temporal enquiries. Motion functions, which predict future object locations based on some analytic functions, can efficiently process short-term predictive range queries, since they can be seamlessly embedded into existing indexing mechanisms. However, motion functions cannot perform long-term predictions since motions of the moving objects might change over time. Other prediction functions such as trajectory patterns and statistical graphic models are more accurate but less efficient. In this dissertation, I also present a pruning mechanism that improve the performance for long-term predictive range queries based on (high-order) Markov chain models learned from historical trajectories. The key to our approach is to devise compressed representations for sparse multi-dimensional matrices, and leverage efficient algorithms for matrix computations. We conduct experiments on both simulated and real world datasets to demonstrate that our methods gain significant improvements over other existing methods. |
See All Seminars