ECMA: An Efficient Convoy Mining Algorithm for Moving Objects

With the popularity of mobile devices equipped with positioning devices, it is convenient to obtain enormous amounts of trajectory data. The development promotes the study of extracting moving patterns from trajectory data of moving objects. One such pattern is the convoy, which refers to a group of objects moving together for a period of time. The existing convoy mining algorithms have a large time cost because they adopt a density-based clustering algorithm over global objects. In this paper, we propose an efficient convoy mining algorithm (ECMA) that adopts the divide-and-conquer methodology. A block-based partition model (BP-Model) is designed to divide objects into multiple maximized connected nonempty block areas (MOBAs). The convoy mining problem is then solved by processing each MOBA sequentially, which significantly reduces the time cost of convoy mining. In the experiments, we evaluate the performance of our algorithm on real-world datasets. The results show that the ECMA is more efficient than existing convoy mining algorithms.