Moving Objects Management : Models, Techniques and Applications

The continued advances in wireless communication and positioning technologies such as GPS have made new data management applications possible, such as location-based services (LBS) that store and manage the continuously changing positions of moving objects. "Moving Objects Management - Models, Techniques and Applications" focuses on moving objects management, from the location management perspective to the exploration of how the continually changing locations affect the traditional database and data mining technology. Specifically, the book describes the topics of moving objects modeling and location updating, indexing and querying, clustering, location uncertainty and privacy issues, as well as their application to intelligent transportation systems. This book is intended for developers of database management systems and mobile applications, research scientists and advanced-level students in computer science and geography. Dr. Xiaofeng Meng is a professor at the School of Information, Renmin University of China; Dr. Jidong Chen is a senior research scientist at EMC Research China, one of the research groups of the EMC Corporation. Cover......Page 1 Moving Objects Management......Page 3 ISBN 9783642131981......Page 4 Foreword......Page 6 Preface......Page 8 Organization of the Book......Page 9 Table of Contents ......Page 12 Acronyms......Page 16 Part I Moving Objects Management Models......Page 19 1.1.1 Mobile Computing......Page 21 1.2 Location-Based Services......Page 22 1.4 Moving Object Databases......Page 24 References......Page 27 2.1 Introduction......Page 31 2.2 Underlying Models......Page 32 2.3.1 Cellular Automata (CA)......Page 35 2.3.2 Structure of GCA......Page 36 2.3.3 Trajectory of GCA......Page 37 2.3.5 Two-Lane GCA......Page 38 2.4 Summary......Page 39 References......Page 40 3.1 Introduction......Page 43 3.2.2 Based on Location Prediction......Page 44 3.3 Proactive Location Update Strategy......Page 45 3.4 Group Location Update Strategy......Page 47 References......Page 51 4.1 Introduction......Page 53 4.2 Underlying Indexing Structures......Page 54 4.2.1 The R-Tree......Page 55 4.2.2 The Grid File......Page 57 4.3 Indexing Moving Objects in Euclidean Space......Page 58 4.3.1 The R-Tree-Based Index......Page 59 4.3.2 The Grid-Based Index......Page 60 4.3.3 The Quad-Tree-Based Index......Page 62 4.4 Indexing Moving Objects in Spatial Networks......Page 69 4.4.1 The Adaptive Unit......Page 70 4.4.2 The Adaptive Network R-Tree (ANR-Tree)......Page 72 4.5.1 Indexing Future Trajectory......Page 75 4.5.2 Indexing History Trajectories......Page 78 4.6 Update-Efficient Indexing Structures......Page 79 References......Page 81 Part II Moving Objects Management Techniques......Page 84 5.1 Introduction......Page 87 5.2 Classifications of Moving Object Queries......Page 88 5.2.1 Based on Spatial Predicates......Page 89 5.2.3 Based on Moving Spaces......Page 90 5.3.1 Incremental Euclidean Restriction......Page 91 5.3.2 Incremental Network Expansion......Page 93 5.4.1 Range Euclidean Restriction......Page 94 5.4.2 Range Network Expansion......Page 95 References......Page 97 6.1 Introduction......Page 99 6.2 Similar Trajectory Queries for Moving Objects......Page 101 6.2.1 Problem Definition......Page 102 6.2.2 Trajectory Similarity......Page 103 6.2.3 Query Processing......Page 105 6.3.1 Problem Definition......Page 107 6.3.2 Cluster-Based Query Preprocessing......Page 108 6.3.3 Density Query Processing......Page 110 6.4.1 Problem Definition......Page 113 6.4.2 Building the Quad-Tree......Page 114 6.4.3 Safe Interval Computation......Page 115 6.4.3.2 Safe Interval of Sparse Leaf Cell......Page 116 6.4.4 Query Processing......Page 119 References......Page 120 7.1 Introduction......Page 123 7.2.2 Road Segment-Based Linear Prediction......Page 124 7.3 Simulation-Based Prediction (SP) Methods......Page 125 7.3.1 Fast-Slow Bounds Prediction......Page 126 7.3.2 Time-Segmented Prediction......Page 128 7.5 Summary......Page 129 References......Page 130 8.1 Introduction......Page 131 8.2 Uncertain Trajectory Modeling......Page 132 8.3.1 Structure of the UTR-Tree......Page 136 8.3.2 Construction and Maintenance of UTR-Tree......Page 139 8.4 Uncertainty Trajectory Querying......Page 140 References......Page 141 Part III Moving Objects Management Applications......Page 143 9.1 Introduction......Page 145 9.2 Moving Objects Management Application Scenarios......Page 146 9.3.1 Hierarchy Aggregation Tree......Page 148 9.3.2 Dynamic Navigation Query Processing......Page 150 9.4 Summary......Page 152 References......Page 153 10.1 Introduction......Page 155 10.2 The System Architecture......Page 156 10.3 Data Model of Transportation Network and Moving Objects......Page 158 10.4.1 Computing the Locations Through Interpolation......Page 163 10.4.2 Querying Moving Objects with Uncertainty......Page 164 10.4.3 Location Prediction in Transportation Networks......Page 166 References......Page 167 11.1 Introduction......Page 169 11.2 Underlying Clustering Analysis Methods......Page 170 11.3.1 Problem Definition......Page 172 11.3.2 Edge-Based Clustering Algorithm......Page 174 11.3.3 Node-Based Clustering Algorithm......Page 177 11.4 Clustering Moving Objects in Spatial Networks......Page 179 11.4.1 CMON Framework......Page 181 11.4.2 Construction and Maintenance of CBs......Page 182 11.4.3.2 Density-based CMON......Page 185 11.4.3.3 K-Partitioning CMON......Page 187 References......Page 188 12.1 Introduction......Page 191 12.2 Privacy Threats in LBS......Page 192 12.3.2 Centralized Architecture......Page 195 12.3.3 Peer-to-Peer Architecture......Page 196 12.4.1 Location K-Anonymity Model......Page 197 12.4.2 p-Sensitivity Model......Page 198 12.4.3 Anonymization Algorithms......Page 201 12.5 Evaluation Metrics......Page 202 References......Page 203 Index......Page 205 We live in an age of rapid technological development. The Internet already affects our lives in many ways. Indeed, we continue to depend more, and more intrinsically, on the Internet, which is increasingly becoming a fundamental piece of societal infrastructure, just as water supply, electricity grids, and transportation networks have been for a long time. But while these other infrastructures are relatively static, the Internet is undergoing swift and fundamental change: Notably, the Internet is going mobile. The world has some 6.7 billion humans, 4 billion mobile phones, and 1.7 billion Internet users. The two most populous continents, Asia and Africa, have relatively low Internet penetration and hold the greatest potentials for growth. Their mobile phone users by far outnumber their Internet users, and the numbers are growing rapidly. China and India are each gaining about half a dozen million new phone users per month. Users across the globe as a whole increasingly embrace mobile Internet devices, with smart phone sales are starting to outnumber PC sales. Indeed, these and other facts suggest that the Internet stands to gain a substantial mobile component. This mega trend towards “mobile” is enabled by rapid and continuing advances in key technology areas such as mobile communication, consumer electronics, g- positioning, and computing. In short, this is the backdrop for this very timely book on moving objects by Xiaofeng Meng and Jidong Chen. Moving Objects Management provides an overview of the field, describing the location management perspective, as well as how locations affect traditional data mining technology. Topics include moving objects modeling and location updating, indexing and querying, clustering, and more.