《移動對象管理:模型、技術與套用(第2版)》是2014年9月清華大學出版社發行部出版的圖書,作者是Xiaofeng Meng(孟小峰)、Zhiming Ding(丁治明)、Jiajie Xu(許佳捷)。
基本介紹
- 中文名:移動對象管理:模型、技術與套用(第2版)
- 作者:Xiaofeng Meng(孟小峰)、Zhiming Ding(丁治明)、Jiajie Xu(許佳捷)
- 出版社:清華大學出版社
- 出版時間:2014年09月1日
- 定價:78 元
- 裝幀:精裝
- ISBN:9787302322863
- 印刷日期: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