Indexing Moving Objects for Predictive Spatio-Temporal Queries Open Access

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 with spatio-temporal indexes that support massive updates and predictive spatio-temporal queries are essential for modern location-based services. 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 but are not suitable for 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.

Table of Contents

1 Introduction. 1

1.1 Velocity-Based Partitioning for Tree-Based Indexes. 4

1.2 Indexing with Uniform Grids. 6

1.3 Processing Predictive Range Queries. 8

1.4 Contribution. 10

1.5 Organization. 11

2 Related Work. 13

2.1 Tree-Based Indexes for MODs. 13

2.2 Grid-Based Indexes for MODs. 16

2.3 Processing Predictive Range Queries. 18

3 The Speed Partitioning Technique. 20

3.1 The Optimization Speed Partitioning Problem. 20

3.1.1 Search space expansion. 21

3.1.2 The optimal speed partitioning. 22

3.2 The Partitioned Indexing System. 26

3.2.1 The optimal speed partitioning. 27

3.2.2 Index update. 31

3.2.3 Query processing. 32

3.3 Experimental Study. 32

3.3.1 Dataset description. 33

3.3.2 Experimental results. 35

4 Uniform Grid Index in Dual Space. 41

4.1 Indexing with Dual Space Grids. 41

4.1.1 Structure overview. 42

4.1.2 Updates. 47

4.1.3 Query processing. 51

4.2 Experimental Study. 55

4.2.1 Dataset description. 56

4.2.2 Evaluation of our methods. 58

4.2.3 Comparison with other methods. 61

5 Markov Chain Based Pruning. 64

5.1 Preliminaries and Problem Denition. 64

5.1.1 Trajectory and path. 64

5.1.2 Predictive range query. 65

5.1.3 The Markov chain model. 66

5.1.4 Sparse matrix storage. 67

5.2 Data Structures. 68

5.2.1 The trajectory grid. 69

5.2.2 The MDIA format. 70

5.2.3 The transition trie. 73

5.3 Algorithms. 75

5.3.1 Markov chain based pruning. 75

5.3.2 Discussions. 81

5.3.3 Multiply with MDIA matrices. 83

5.4 Experimental Study. 90

5.4.1 Experimental setup. 90

5.4.2 Evaluation of our methods. 92

5.4.3 Comparison with other methods. 97

6 Conclusion and Future Work. 100

6.1 Summary. 100

6.2 Future Work. 102

About this Dissertation

Rights statement

• Permission granted by the author to include this thesis or dissertation in this repository. All rights reserved by the author. Please contact the author for information regarding the reproduction and use of this thesis or dissertation.

School	Laney Graduate School
Department	Math and Computer Science
Degree	PhD
Submission	Dissertation
Language	English
Research Field	Computer Science
Keyword	velocity-based partitioning Markov chain spatio-temporal index moving object predictive query
Committee Chair / Thesis Advisor	Xiong, Li, Emory University Sunderam, Vaidy S, Emory University
Committee Members	Vigfusson, Ymir , Emory University Mokbel, Mohamed, University of Minnesota - Twin Cities

Last modified

Primary PDF

Thumbnail	Title	Date Uploaded	Actions
	Indexing Moving Objects for Predictive Spatio-Temporal Queries ()	2018-08-28 13:56:51 -0400	Press to Select an action Download

Supplemental Files

Thumbnail	Title	Date Uploaded	Actions
	figure.zip ()	2018-08-28 14:00:03 -0400	Press to Select an action Download