Research On Moving-together Pattern Mining Technology Over Spatio-temporal Trajectory Data

With the increase of mobile devices equipped with GPS and the development of location-acquisition technologies,people can easily obtain massive spatio-temporal trajectory data.These data represent the mobility of a diversity of people,animals,and vehicles.Trajectory data mining technologies enable people to obtain a large amount of usable knowledge from these data,which can be applied in a wide range of applications and services,including animal behavior study,urban planning,social recommendations,and location-aware advertising,to name but a few.One of the research hotspots in trajectory data mining is moving-together pattern mining,which aims to find objects moving together from trajectory data.Therefore,it is very important to propose suitable models and design efficient mining algorithms.In this thesis,three innovations are proposed for the moving-together pattern mining technology over spatio-temporal trajectory data.(1)A new moving-together pattern called Loose Tracking Behavior is proposed to detect moving objects that track a given query trajectory.We develop the basic Loose Tracking Behavior Detection(LTBD)algorithm and its improved algorithm(LTBD+)to solve the problem.In LTBD+,we develop a prefix tree index structure for the trajectories encoded by Geohash algorithm to enhance the detection efficiency.Theoretical analysis and experimental results demonstrate the effectiveness and efficiency of our methods.(2)This thesis proposes an Efficient Convoy Mining Algorithm(ECMA)where a Block-based Partition Model(BP-Model)is designed to divide objects into multiple Maximized Connected Non-empty Block Areas(MOBAs).The convoy mining problem is then conquered by processing each MOBA sequentially,which significantly reduces the time cost of convoy mining.Theoretical analysis and experimental results demonstrate that ECMA is much more efficient than the existing convoy mining algorithms.(3)A prototype system is designed to test and verify the proposed loose tracking behavior detection algorithm and efficient convoy mining algorithm.