移動對象管理：模型、技術與套用（第2版）

《移動對象管理：模型、技術與套用（第2版）》是2014年清華大學出版社發行部出版的圖書，作者是孟小峰。

基本介紹

• 書名：移動對象管理：模型、技術與套用（第2版）
• 作者：Xiaofeng Meng（孟小峰）
• ISBN：9787302322863
• 定價：78元
• 出版社：清華大學出版社
• 出版時間：2014年09月 
• 裝幀：精裝
• 印刷日期：2014-8-29

圖書簡介

移動通信技術的持續發展催生了基於位置服務（LBS）的廣泛套用。這類新型套用需要存儲並管理移動對象不斷變化的位置信息。本書針對移動對象數據管理問題，從位置服務的角度分析頻繁的位置變化給傳統資料庫所帶來的挑戰。本書系統介紹了移動對象建模與位置跟蹤、索引、查詢處理與最佳化、軌跡聚類、不確定性處理、隱私保護等領域的最新研究成果，以及相關成果在智慧型交通系統中的套用。
本書的讀者對象為高等院校計算機專業的本科生、研究生、教師，科研機構的研究人員以及相關領域的開發人員等。

目錄

1 Introduction ................................................................. 1

1.1 Concept of MovingObjects Data Management .................... 1

1.2 ApplicationsofMovingObjectsDatabase.......................... 2

1.3 Key Technologiesin Moving Objects Database .................... 3

1.3.1 MovingObjects Modeling ................................. 3

1.3.2 Location Trackingof Moving Objects..................... 4

1.3.3 MovingObjects Database Indexes......................... 6

1.3.4 UncertaintyManagement .................................. 7

1.3.5 MovingObjectsDatabaseQuerying....................... 7

1.3.6 Statistical Analysis and Data Mining of MovingObject Trajectories ................................ 8

1.3.7 LocationPrivacy............................................ 9

1.4 Applicationsof Mobile Data Management ......................... 9

1.5 Purposeof This Book ................................................ 10

References.................................................................... 10

2 Moving Objects Modeling ................................................. 15

2.1 Introduction........................................................... 15

2.2 Representative Models............................................... 17

2.2.1 MovingObject Spatio-Temporal(MOST) Model ........ 17

2.2.2 Abstract Data Type (ADT) with Network................. 18

2.2.3 Graph of Cellular Automata (GCA) ....................... 20

2.3 DTNMOM............................................................ 21

2.4 ARS-DTNMOM ..................................................... 26

2.5 Summary.............................................................. 30

References.................................................................... 30

3 Moving Objects Tracking .................................................. 33

3.1 Introduction........................................................... 33

3.2 Representative Location Update Policies ........................... 34

3.2.1 Threshold-BasedLocation Updating ...................... 34

3.2.2 Motion Vector-Based Location Updating ................. 35

v

Contents

3.2.3 Group-BasedLocation Updating .......................... 35

3.2.4 Network-ConstrainedLocation Updating ................. 36

3.3 Network-ConstrainedMoving Objects Modeling and Tracking ... 36

3.3.1 Data Model for Network-ConstrainedMovingObjects .. 36

3.3.2 Location Update Strategies for Network-ConstrainedMoving Objects .................... 38

3.4 A Traf.c-AdaptiveLocation Update Mechanism .................. 40

3.4.1 The AutonomicANLUM (ANLUM-A) Method ......... 42

3.4.2 The Centralized ANLUM (ANLUM-C) Method ......... 44

3.5 A Hybrid Network-ConstrainedLocation Update Mechanism .... 47 3.6 Summary.............................................................. 48

References.................................................................... 49

4 Moving Objects Indexing .................................................. 51

4.1 Introduction........................................................... 51

4.2 Representative Indexing Methods ................................... 53

4.2.1 The R-Tree.................................................. 53

4.2.2 The TPR-Tree............................................... 54

4.2.3 The Spatio-TemporalR-Tree............................... 56

4.2.4 The Trajectory-BundleTree................................ 57

4.2.5 The MON-Tree ............................................. 58

4.3 Network-Constrained Moving Object Sketched-TrajectoryR-Tree ................................. 59

4.3.1 Data Model.................................................. 60

4.3.2 IndexStructure.............................................. 61

4.3.3 IndexUpdate................................................ 64

4.3.4 Query........................................................ 65

4.4 Network-Constrained Moving Objects Dynamic Trajectory R-Tree ......................................... 67

4.4.1 IndexStructure of NDTR-Tree ............................ 67

4.4.2 Active TrajectoryUnit Management ...................... 68

4.4.3 Constructing, Dynamic Maintaining, and Queryingof NDTR-Tree ................................... 70

4.5 Summary..............................................................71

References.................................................................... 72

5 Moving Objects Basic Querying .......................................... 73

5.1 Introduction........................................................... 73

5.2 Classi.cations of Moving Object Queries .......................... 74

5.2.1 Based on Spatial Predicates................................ 74

5.2.2 Based on TemporalPredicates ............................. 76

5.2.3 Based on Moving Spaces................................... 76

5.3 Point Queries ......................................................... 77

5.4 NN Queries ........................................................... 78

5.4.1 IncrementalEuclideanRestriction......................... 78

5.4.2 IncrementalNetworkExpansion........................... 79

Contents vii

5.5 Range Queries........................................................ 81

5.5.1 Range EuclideanRestriction ............................... 81

5.5.2 RangeNetworkExpansion................................. 82

5.6 Summary.............................................................. 83

References.................................................................... 84

6 Moving Objects Advanced Querying ..................................... 87

6.1 Introduction........................................................... 87

6.2 Similar Trajectory Queries for MovingObjects .................... 89

6.2.1 Problem De.nition ......................................... 90

6.2.2 TrajectorySimilarity ....................................... 92

6.2.3 Query Processing ........................................... 94

6.3 Convoy Queries on MovingObjects ................................ 95

6.3.1 Spatial Relations AmongConvoy Objects ................ 96

6.3.2 CoherentMovingCluster(CMC).......................... 96

6.3.3 Convoy Over Simpli.ed Trajectory (CoST)............... 96

6.3.4 Spatio-TemporalExtension (CoST*)...................... 98

6.4 Density Queries for MovingObjects in Spatial Networks ......... 99

6.4.1 Problem De.nition ......................................... 99

6.4.2 Cluster-Based Query Preprocessing ....................... 100

6.4.3 DensityQueryProcessing.................................. 102

6.5 ContinuousDensity Queries for Moving Objects .................. 105

6.5.1 Problem De.nition ......................................... 106

6.5.2 Building the Quad-Tree .................................... 107

6.5.3 Safe IntervalComputation ................................. 108

6.5.4 Query Processing ........................................... 112

6.6 Summary.............................................................. 112

References.................................................................... 113

7 Trajectory Prediction of Moving Objects ................................ 117

7.1 Introduction........................................................... 117

7.2 UnderlyingLinear Prediction (LP) Methods........................ 118

7.2.1 GeneralLinear Prediction.................................. 118

7.2.2 RoadSegment-BasedLinearPrediction................... 118

7.2.3 Route-Based Linear Prediction ............................ 119

7.3 Simulation-Based Prediction (SP) Methods ........................ 120

7.3.1 Fast-Slow BoundsPrediction .............................. 120

7.3.2 Time-SegmentedPrediction................................ 123

7.4 Uncertain Path Prediction Methods ................................. 123

7.4.1 Preliminary.................................................. 124

7.4.2 Uncertain Trajectory Pattern Mining Algorithm .......... 126

7.4.3 Frequent Path Tree.......................................... 127

7.4.4 Trajectory Prediction ....................................... 130

7.5 OtherNonlinearPredictionMethods................................ 130

7.6 Summary.............................................................. 131

References.................................................................... 131

viii Contents

8 Uncertainty Management in Moving Objects Database ............... 133

8.1 Introduction........................................................... 133

8.2 RepresentativeModels............................................... 135

8.2.1 2D-EllipseModel........................................... 135

8.2.2 3D-CylinderModel......................................... 136

8.2.3 Modelthe Uncertainty in Database........................ 137

8.3 Uncertain Trajectory Management .................................. 140

8.3.1 Uncertain TrajectoryModeling ............................ 140

8.3.2 DatabaseOperationsforUncertaintyManagement....... 144

8.4 Summary.............................................................. 147

References.................................................................... 147

9 Statistical Analysis on Moving Object Trajectories..................... 149

9.1 Introduction........................................................... 149

9.2 Representative Methods.............................................. 151

9.2.1 Based on FCDs ............................................. 151

9.2.2 Based on MODs ............................................ 151

9.3 Real-Time Traf.c Analysis on Dynamic Transportation Networks 152

9.3.1 ModelingDynamic TransportationNetworks............. 152

9.3.2 Real-Time Statistical Analysis of Traf.c Parameters..... 156

9.4 Summary.............................................................. 160 References.................................................................... 161

10 Clustering Analysis of Moving Objects .................................. 163

10.1 Introduction........................................................... 163

10.2 UnderlyingClusteringAnalysisMethods........................... 164

10.3 Clustering Static Objects in Spatial Networks...................... 166

10.3.1 Problem De.nition ......................................... 167

10.3.2 Edge-BasedClusteringAlgorithm......................... 168

10.3.3 Node-Based Clustering Algorithm......................... 172

10.4 Clustering MovingObjects in Spatial Networks.................... 175

10.4.1 CMON Framework......................................... 176

10.4.2 Constructionand Maintenance of CBs .................... 177

10.4.3 CMONConstructionwithDifferentCriteria.............. 179

10.5 Clustering TrajectoriesBased on Partition-and-Group ............. 183

10.5.1 Partition-and-GroupFramework........................... 183

10.5.2 Region-Based Cluster ...................................... 186

10.5.3 Trajectory-BasedCluster................................... 187

10.6 Clustering TrajectoriesBased on Features Other Than Density ... 188

10.6.1 Preliminary.................................................. 188

10.6.2 Big Region Reconstruction................................. 190

10.6.3 ParametersDeterminationinRegionRe.nement......... 193

10.7 Summary.............................................................. 193

References.................................................................... 194

Contents

11 Dynamic Transportation Navigation ..................................... 197

11.1 Introduction........................................................... 197

11.2 TypicalDynamicTransportationNavigationStrategies............ 199

11.2.1 D* Algorithm ............................................... 199

11.2.2 HierarchyAggregationTree Based Navigation ........... 200

11.3 IncrementalRouteSearchStrategy.................................. 201

11.3.1 Problem De.nitions ........................................ 201

11.3.2 Pre-computation ............................................ 203

11.3.3 Top-KIntermediate Destinations .......................... 204

11.3.4 Route Search and Update .................................. 206

11.4 Summary.............................................................. 207

References.................................................................... 207

12 Location Privacy ............................................................ 211

12.1 Introduction........................................................... 211

12.2 Privacy Threats in LBS .............................................. 212

12.3 System Architecture.................................................. 215

12.3.1 Non-cooperativeArchitecture.............................. 215

12.3.2 Centralized Architecture ................................... 216

12.3.3 Peer-to-Peer Architecture .................................. 217

12.4 Location AnonymizationTechniques ............................... 217

12.4.1 Location K-AnonymityModel ............................ 218

12.4.2 p-Sensitivity Model ........................................ 219

12.4.3 AnonymizationAlgorithms ................................ 222

12.5 Evaluation Metrics ................................................... 223

12.6 Summary.............................................................. 224

References.................................................................... 224

Index ............................................................................... 227

序言

The widespread use of mobile positioning tools like GPS and smart mobile phones nowadays has aroused great interests in location-based services (LBS) that have to store and manage continuously changing positions of moving objects. This book gives a comprehensive and complete view of a moving objects database and introduces how it is used in LBS and transportation applications. It aims at moving objects management, from the location management perspective to analyze how the continually changing locations affect the traditional database and data mining technology. Speci.cally, the book describes the cutting edge technologies related to topics like moving objects modeling and location tracking, indexing and querying, trajectory prediction, location uncertainty, traf.c .ow analysis, objects clustering, traf.c aware navigation and privacy issues as well as their application to intelligent transportation systems.

Previous studies mostly focused on moving objects database in free space. They assumed that the movement of the objects is unconstrained and based on Euclidean spaces. However, in the real world, objects usually move within spatially constrained networks, e.g., vehicles move on road networks. Overlooking this reality often leads to unrealistic data modeling and inaccurate query results. The content in this book focuses mainly on the moving objects within spatial networks, which is more practical. By exploiting the network feature of spatial networks, this book introduces models, techniques, and applications of moving objects management in a spatial network.

This book is intended to help readers understand the main technologies in moving object management and apply them to LBS and transportation applications. Compared with the .rst edition, this book particularly focuses on the constrained network environments, and it has made substantial changes to each chapter so that the cutting edge techniques in this .eld are included. With its accessible style and emphasis on practicality, the book presents new concepts and techniques for managing continuously moving objects. Database management systems developers,

Preface

mobile applications developers, and applied R&D researchers will .nd the study an essential companion for new concepts, development strategies, and application models associated with this kind of changing location data. The book:

. Presents a comprehensive architecture of moving object management, which includes not only basic theories and new concepts but also practical technologies and applications

. Describes a set of new database techniques in modeling, tracking, indexing, querying of moving objects, traf.c .ow analysis, as well as data mining techniques in clustering analysis of moving objects

. Introduces some new research issues in location privacy and uncertainty man-agement of moving objects, which are topics of major interest in this .eld

. Provides typical applications of moving objects management in intelligent transportation systems