Research On Algorithms For Mining And Evaluating Moving Clusters Pattern From Spatio-Temporal Trajectories Streams

Moving clusters pattern discovery from spatial-temporal trajectory data is an important research topic in the field of spatial-temporal trajectory pattern mining,which can be widely used in intelligent traffic management,public safety services and animal behavior research and so on.In recent years,with the development of sensor network technology,communication technology,positioning technology and the widely application of mobile intelligent terminals such as various positioning devices and mobile phones,the spatio-temporal data can be collected in real time with the form of trajectory streams.Spatio-temporal trajectory streams is real-time,quickly update and unbound.These features greatly increase the difficulty of storing the data and require high timeliness.In order to solve the problem of moving clusters pattern discovery from massive trajectory streams,this thesis studies the algorithm for mining and evaluating moving clusters pattern from trajectory streams.The main innovative contributions of this thesis are as follows:1.Propose framework MCStream(Moving Clusters pattern discovery from trajectory Streams)for mining moving clusters pattern.The framework is based on the existing various moving clusters patterns.By carrying out three stages:acquiring spatial relationship,acquiring related-clusters and updating moving clusters pattern,the framework can discover the moving clusters pattern.In the phase of spatial relationship acquisition,in order to improve the efficiency of the algorithm,the structure moving micro-group is proposed to maintain stable relationships among small groups.At the same time,the related-cluster is obtained using the containment relationship of clusters between adjacent timestamps.To avoid recalculation and improving the efficiency of the algorithm,the information of the related-cluster is used to update the pattern of the previous timestamp.2,Propose algorithm GMCStream(Gradual Moving object Clusters discovery from trajectory Stream)for mining gradual moving object clusters pattern from trajectory streams.Based on the framework MCStream,algorithm GMCStream introduces the time window technology and processes the streams in the time window to quickly mining gradual moving object clusters pattern by taking advantages of the characteristic of relaxing time.Furthermore,in order to reduce ineffective intersection operation in the process of pattern updating,two pruning rules are utilized to optimize the intersection operation by using the characteristics of gradual property,which reduces the computational load in the process of intersection and improves the efficiency of mining algorithm.3.Present parallel algorithm of algorithm GMCStream denoted as PGMCStream(Parallel Gradual Moving object Clusters discovery from trajectory Stream)based on Spark Streaming computing technology to mine gradual moving object clusters pattern from trajectory streams.The continuous arrival trajectory streams is divided into batches in minutes.The streams in each batch is distributed to each node and computed simultaneously by multiple computing nodes in the cluster,which improves the efficiency of the algorithm and realizes the parallel mining of gradual moving object clusters pattern.4.Propose algorithms RWR-Ranking and WRWR-Ranking to evaluate moving clusters pattern.With the utilization of relationship between space attribute and POI,the algorithm RWR-Ranking uses random walk with restart to rank moving clusters pattern.Furthermore,combining temporal and spatial factors,algorithm WRWR-Ranking is proposed which uses weighted random walk with restart to rank moving clusters pattern.