如今定位科技愈发发达，有关运动物体的数据信息也越来越多，因此，在大量的运动数据之间寻找一起运动的物体成为一个重要的研究方向。然而，现存的方法对于是否在一起运动的划分标准上存在很多限制，比如，物体必须在连续的一段时间内（k个时间戳）一直保持位置相近才算一起运动，而本文提出的算法旨在解决在某一时间汇聚，而其他时间也许分离的运动情况。
举例如下图，令k=3，从实际来看，这四条轨迹实际上是一个cluster，但如果按照现存做法，由于o1,o2,o3,o4没有一直在一起，所以不能算作在一起运动，这就与实际情况相违背。而如果按照本文的算法，对是否一起运动的标准放松一些要求，允许物体可以短暂离开一段时间，但是在其他时间内都汇聚在一起，那么结果就和真实情况相符。
寻找moving object cluster有两种方式，除了上图中提到的寻找固定时刻的object外，还有观察object trajectory的方法。然而，对于object trajectory的方式，如下图所示，有时两者轨迹看起来相差许多，然而若选定固定时间戳后会发现两者实际上是一起运动的。
作者在本文中将一起运动的物体族称为moving object cluster，并定义如下：1>object彼此间物理位置相近 2>至少需要在mininum time duration内保证一起运动。
Contributions：1> 提出swarm的概念 2>提出ObjectGrowth算法用于高效寻找swarm。3>算法无论是在真实数据还是合成数据面前都表现出有效性和高效性。
（一）swarm概念：
作者提出了一种名为swarm的运动模式，是moving cluster的更为通用的一种模型。swarm也可以表示为一个（O，T）对，比如图1中的({o1,o3,o4},{t1,t3,t4})。一个（O，T）对包含至少min(0)个物体（O>min(o)），至少一起运动min(t)时间（T>min(t)）。但是，如果仅用（O,T）对来描述可能会出现重复，比如在图1中，我们除了说01,03,04一起运动外，我们同时可以说01,03一起运动，01,04一起运动，03,04一起运动。这样就带来了redundant。为了解决这一问题，作者给出了一个closed swarm的概念，closed swarm表示这个（O,T）对的O和T都不能继续扩展了。——最终目标就变成了寻找所有的closed swarm。
如上图所示，若min（o） = 2 and min（t） = 2，则实际上可以有15个swarm，比如({o1, o2}, {t1, t2}), ({o1, o4}, {t1, t2}), ({o2, o4}, {t1, t3, t4})等等。但是({o2,o4}, {t1,t2}) and ({o2,o4}, {t2,t3,t4})都是redundant的，因为他们都可以进行扩展。所以实际上这个图中只有两个closed swarm，分别是({o2, o4}, {t1, t2, t3, t4}) 和({o1,o2,o4}, {t1,t2,t4}).
（二）ObjectGrowth算法：
由图三所示，初看点和时间的对应结构，swarm的个数应该是指数级别个：
然而，经过作者证明，如果object给定，对应的最大timeset个数是可以被唯一指定的。swarm的个数就由此可以被削减至2的Odb次幂。但是这个搜寻空间还是很大，作者在本文中采取了深度搜索，前向优先的规则，并提出了两种剪枝的办法用于加速搜索。
两种方法分别是Apriori Pruning和Backward Pruning。其中，Apriori Pruning表示一旦向下搜寻时发现T<min(t)则停止。（因为在object个数较少时都不能满足T<min(t)，则继续向下搜索则更不可能满足）Backward Pruning表示一旦发现目前寻找到的swarm存在一个超集，并且这个超集的最大对应时间和当前的相同则停止。（证明这不是一个closed swarm）。
经过这两种剪枝后，剩下的也不一定是closed swarms（比如14没有被剪枝，145也没有被剪枝，此时也许145才是closed swarm而14不是，所以前面两种剪枝方法不能确保结果都是closed swarms）。暴力搜索剩下的swarm虽然可以解决问题，但是时间成本太高，所以作者提出了一种Forward Closure Checking方法，即寻找是否存在另一个object集与当前object集只差一个object且T相同，如果存在的话就删掉object小的一个。这种方式不会像剪枝方法一样暂停DFS过程，但是在寻找过程中就嵌入着checking过程，大大减少了寻找closed swarm时间。
此时复杂度压缩至：
（三）实验过程
本文章的demo system在http://dm.cs.uiuc.edu/movemine/上，实验数据来自于http://www.movebank.org的real animal data。实验结果分Effectiveness和Efficiency两部分。注意：在每次寻找OT对时，要先对Object进行点聚类如图3，本篇文章采用了DBSCAN的方法。
1.Effectiveness：(DNSCAN:MinPts= 5, Eps = 0.001)
实验中，min(o) = 2，min(t) = 0.5，结果发现了7个closed swarm，其中一个如下（蓝色部分，剩余的线条为原始行动路径）：
2.Efficiency：(DNSCAN:MinPts= 3, Eps = 300)
实验中为了检验efficiency，作者采用了合成数据（using Brinkhoff’s network-based generator of moving objects）。共计500 objects， 105 timestamps。并且通过使用ObjectGrowth+算法和VG-Growth算法对比来评估效率。（VG-Growth——previous work addressing the non-consecutive timestamps issue.）
下图是运行时间和closed swarm图，横轴分别是min(0),min(t),O,T。
