BP-Model-based convoy mining algorithms for moving objects

摘要

It is convenient to obtain enormous trajectory data by using the positioning chips equipped mobile devices, nowadays. The study of extracting moving patterns from trajectory data of moving objects is becoming a hot spot. Convoy is one of the popular studied patterns, which refers to a group of objects moving together for a period of time. The existing convoy mining algorithms have a large cost because they all adopt a quadratic density-based clustering algorithm over the global objects. In this paper, we propose BP-Model-based convoy mining algorithms which optimize the mining in spatial dimension by adopting the divide-and-conquer methodology. A Block-based Partition Model (BP-Model) is designed to divide objects into multiple Maximized Connected Non-empty Block Areas (MOBAs). On the basis of BP-model, a baseline convoy mining algorithm (BCMA) is firstly introduced to efficiently mine convoys by processing each MOBA separately. To further accelerate the mining, an optimized convoy mining algorithm (OCMA) is proposed by adopting the idea of filtering out the invalid MOBAs that have no contribution for mining convoys. In the experiments, we evaluate the performance of our algorithms on the real-world datasets. The result shows that the proposed algorithms are much more efficient than the existing convoy mining algorithms.