Moving Objects Management (eBook)

Title Page 2
Copyright Page 3
Foreword 4
Preface 6
Organization of the Book 7
Table of Contents 10
Acronyms 14
Part I Moving Objects Management Models 16
Chapter 1 Introduction 18
1.1 Background 18
1.1.1 Mobile Computing 18
1.1.2 Positioning Techniques 19
1.2 Location-Based Services 19
1.3 Mobile Data Management 21
1.4 Moving Object Databases 21
References 24
Chapter 2 Moving Objects Modeling 27
2.1 Introduction 27
2.2 Underlying Models 28
2.3 Graphs of Cellular Automata Model 31
2.3.1 Cellular Automata (CA) 31
2.3.2 Structure of GCA 32
2.3.3 Trajectory of GCA 33
2.3.4 Transition of GCA 34
2.3.5 Two-Lane GCA 34
2.4 Summary 35
References 36
Chapter 3 Moving Objects Updating 38
3.1 Introduction 38
3.2 Underlying Update Strategies 39
3.2.1 Based on Threshold 39
3.2.2 Based on Location Prediction 39
3.2.3 Based on Object Grouping 40
3.3 Proactive Location Update Strategy 40
3.4 Group Location Update Strategy 42
3.5 Summary 46
References 46
Chapter 4 Moving Objects Indexing 47
4.1 Introduction 47
4.2 Underlying Indexing Structures 48
4.2.1 The R-Tree 49
4.2.2 The Grid File 51
4.2.3 The Quad-Tree 52
4.3 Indexing Moving Objects in Euclidean Space 52
4.3.1 The R-Tree-Based Index 53
4.3.2 The Grid-Based Index 54
4.3.3 The Quad-Tree-Based Index 56
4.4 Indexing Moving Objects in Spatial Networks 63
4.4.1 The Adaptive Unit 64
4.4.2 The Adaptive Network R-Tree (ANR-Tree) 66
4.5 Indexing Past, Present, and Future Trajectories 69
4.5.1 Indexing Future Trajectory 69
4.5.2 Indexing History Trajectories 72
4.6 Update-Efficient Indexing Structures 73
4.7 Summary 75
References 75
Part II Moving Objects Management Techniques 78
Chapter 5 Moving Objects Basic Querying 80
5.1 Introduction 80
5.2 Classifications of Moving Object Queries 81
5.2.1 Based on Spatial Predicates 82
5.2.2 Based on Temporal Predicates 83
5.2.3 Based on Moving Spaces 83
5.3 NN Queries 84
5.3.1 Incremental Euclidean Restriction 84
5.3.2 Incremental Network Expansion 86
5.4 Range Queries 87
5.4.1 Range Euclidean Restriction 87
5.4.2 Range Network Expansion 88
5.5 Summary 90
References 90
Chapter 6 Moving Objects Advanced Querying 92
6.1 Introduction 92
6.2 Similar Trajectory Queries for Moving Objects 94
6.2.1 Problem Definition 95
6.2.2 Trajectory Similarity 96
6.2.3 Query Processing 98
6.3 Density Queries for Moving Objects in Spatial Networks 100
6.3.1 Problem Definition 100
6.3.2 Cluster-Based Query Preprocessing 101
6.3.3 Density Query Processing 103
6.4 Continuous Density Queries for Moving Objects 106
6.4.1 Problem Definition 106
6.4.2 Building the Quad-Tree 107
6.4.3 Safe Interval Computation 108
6.4.3.1 Safe Interval of Dense Leaf Cell 109
6.4.3.2 Safe Interval of Sparse Leaf Cell 109
6.4.4 Query Processing 112
6.5 Summary 113
References 113
Chapter 7 Trajectory Prediction of Moving Objects 116
7.1 Introduction 116
7.2 Underlying Linear Prediction (LP) Methods 117
7.2.1 General Linear Prediction 117
7.2.2 Road Segment-Based Linear Prediction 117
7.2.3 Route-Based Linear Prediction 118
7.3 Simulation-Based Prediction (SP) Methods 118
7.3.1 Fast-Slow Bounds Prediction 119
7.3.2 Time-Segmented Prediction 121
7.4 Other Non-Linear Prediction Methods 122
7.5 Summary 122
References 123
Chapter 8 Uncertainty of Moving Objects 124
8.1 Introduction 124
8.2 Uncertain Trajectory Modeling 125
8.3 Uncertain Trajectory Indexing 129
8.3.1 Structure of the UTR-Tree 129
8.3.2 Construction and Maintenance of UTR-Tree 132
8.4 Uncertainty Trajectory Querying 133
8.5 Summary 134
References 134
Part III Moving Objects Management Applications 136
Chapter 9 Dynamic Transportation Navigation 138
9.1 Introduction 138
9.2 Moving Objects Management Application Scenarios 139
9.3 Dynamic Transportation Navigation 141
9.3.1 Hierarchy Aggregation Tree 141
9.3.2 Dynamic Navigation Query Processing 143
9.3.3 Dynamic Navigation System Architecture 145
9.4 Summary 145
References 146
Chapter 10 Dynamic Transportation Networks 147
10.1 Introduction 147
10.2 The System Architecture 148
10.3 Data Model of Transportation Network and Moving Objects 150
10.4 Querying Moving Objects in Transportation Networks 155
10.4.1 Computing the Locations Through Interpolation 155
10.4.2 Querying Moving Objects with Uncertainty 156
10.4.3 Location Prediction in Transportation Networks 158
10.5 Summary 159
References 159
Chapter 11 Clustering Analysis of Moving Objects 161
11.1 Introduction 161
11.2 Underlying Clustering Analysis Methods 162
11.3 Clustering Static Objects in Spatial Networks 164
11.3.1 Problem Definition 164
11.3.2 Edge-Based Clustering Algorithm 166
11.3.3 Node-Based Clustering Algorithm 169
11.4 Clustering Moving Objects in Spatial Networks 171
11.4.1 CMON Framework 173
11.4.2 Construction and Maintenance of CBs 174
11.4.3 CMON Construction with Different Criteria 177
11.4.3.1 Distance-based CMON 177
11.4.3.2 Density-based CMON 177
11.4.3.3 K-Partitioning CMON 179
11.5 Summary 180
References 180
Chapter 12 Location Privacy 182
12.1 Introduction 182
12.2 Privacy Threats in LBS 183
12.3 System Architecture 186
12.3.1 Non-Cooperative Architecture 186
12.3.2 Centralized Architecture 186
12.3.3 Peer-to-Peer Architecture 187
12.4 Location Anonymization Techniques 188
12.4.1 Location K-Anonymity Model 188
12.4.2 p-Sensitivity Model 189
12.4.3 Anonymization Algorithms 192
12.5 Evaluation Metrics 193
12.6 Summary 194
References 194
Index 196