The problem of finding moving objects that travel together has been extensively studied over the past decade using data mining algorithms. Some representative studies include Flock [1]}, Convoy [2]}, Swarm [3]} and Gathering [4]}. The authors in [2]} define convoy to describe a generic pattern of traveling companions of any shape. A convoy is a group of at least m moving objects that are density-connected with respect to a distance e during at least k consecutive time points. A simple algorithm for discovering convoys is to perform a density-connected cluster algorithm at each time point and maintain convoy candidates who have at least k clusters during consecutive time points. Then for each candidate, an intersection of its clusters is conducted to test whether there are at least m objects shared by all the clusters. To overcome the high computational complexity, the authors propose to first extract candidate convoys based on simplified trajectories and then decide whether each candidate is indeed qualified in the refinement step. The pattern of swarms [3]} further relaxes the constraint of convoys by defining traveling companions as moving objects that move within density-connected clusters for at least k time points that are possibly non-consecutive. The goal of the work is to discover all closed swarms, such that neither the object set nor the number of time points of the swarms can be enlarged. As the number of candidate closed swarms is prohibitively huge, the authors propose two pruning strategies to effectively reduce the search space.
