Zhenhui Li, Bolin Ding, Jiawei Han, and Roland Kays
Recent improvements in positioning technology make massive moving object data widely available. One important analysis is to ﬁnd the moving objects that travel together. Existing methods put a strong constraint in deﬁning moving object cluster, that they require the moving objects to stick together for consecutive timestamps. Our key observation is that the moving objects in a cluster may actually diverge temporarily and congregate at certain timestamps.
Motivated by this, we propose the concept of swarm which captures the moving objects that move within arbitrary shape of clusters for certain timestamps that are possibly nonconsecutive. The goal of our paper is to ﬁnd all discriminative swarms, namely closed swarm. While the search space for closed swarms is prohibitively huge, we design a method, ObjectGrowth, to eﬃciently retrieve the answer. In ObjectGrowth, two eﬀective pruning strategies are proposed to greatly reduce the search space and a novel closure checking rule is developed to report closed swarms on-the-ﬂy. Empirical studies on the real data as well as large synthetic data demonstrate the eﬀectiveness and eﬃciency of our methods.
In Proceedings of the VLDB Endowment, the 36th International Conference on Very Large Data Bases (VLDB 2010)
Publisher Very Large Data Bases Endowment Inc.