Research On Key Technologies Of Spatial-temporal Data Management In Moving Object Database

Along with the development of wireless sensor network and location' service and population of wireless handheld devices and in-car devices, more and more application system are required to support the management of moving objects.It leads to the advent of the Moving Object Database (MOD).The techniques in traditional database are focused on optimizing the querying in static objects,which couldn't hold efficient performance in management of moving objects.Therefore,it is necessary to do some works in MOD.This thesis explores the key technologies in two aspects of MOD system.The first is how to improving the efficiency of updates in indexing structure of MOD.In this aspect,my research is mainly focused on indexing the current and future position of moving objects on road network;the second is how to detect the outlier from trajectory dataset efficiently and effectively.In this aspect,we focus on detecting outlier trajectories or outlier points from trajectory datasets,which consists of the trajectories with long path.Indexing structure is one of key technologies in moving objects database system.In this thesis,a novel index structure,Group Update & Time Parameter R-Tree(GTR-Tree,for short),is proposed firstly.In this scheme,all updates are categorized three groups:span-updates,after which update object stays at another road,constant-speed-updates,after which update object still stay at original road and its velocity is same as original velocity,and variable-speed-updates,after which update object still stay at original road and its velocity isn't same as original velocity,and different' update group leads to different processions.All insertions are buffered to process in group for share the same path and deletion information is maintained by obsolete object table until the leaf node that obsolete entry resides is accessed.Next,facing to the inefficiency in CPU time of TGR-Tree because of obsolete object table,a modified GTR-Tree, MGTR-Tree for short,is presented.MGTR-Tree divides each update process into two sub-processes:insertion sub-process,which inserts insertion entry and deletion sub-process,which inserts deletion entry,and then inserting deletion entry replace the obsolete object table to maintain deleting information.Finally,as to the limitation of GTR-Tree and MGTR-Tree of the large requirement in main memory,a disk-based GTR-Tree,DGTR-Tree for short,is proposed,which use disk space to buffer insertion entry and deletion entry.Outlier detection in trajectory dataset is one of key topic in trajectory data mining.This thesis firstly explores the feature of trajectory data and existing algorithm of outlier trajectory detecting;and aiming the defect of only comparing the shape between two trajectory segments in existing algorithm,this thesis presented a novel distance measure of trajectory segment,which is based on Minimum Hausdorff Distance under Translation that is used to compute the comparisons between two point sets,and compares the trajectory segments from the shape and local movement pattern(speed and direction).Based on this distance measure,a novel outlying trajectory detecting algorithm is proposed,which uses R-Tree and the point distance feature matrix of trajectory point between two trajectories to find out all trajectory segments pairs,in which trajectory segments are close each other.Next,along with the number of the points,which form a trajectory,become large,detecting outlying points in trajectory become more meaningful to some users.Based on this,this thesis presents a novel outlier detecting algorithm,which is objective to detecting outlying points in trajectory.This algorithm introduces the concept of Local Outlier Degree (LOD for short),which denotes the abnormal degree of one point.The local includes two points:(1) comparing unit is trajectory segment with fixed size, not a trajectory;(2) trajectory segment only compares with the trajectory segment within fixed neighborhood.In order to evaluate the performance of methodologies and algorithms proposed in this thesis,a series of experiments are designed and implemented,and comparisons between the methods presented in this thesis and other previously proposed algorithms are done.The results prove our algorithms hold more efficient and effective than others.