Finding All Maximal Duration Flock Patterns in High-dimensional Trajectories
Hiroki Arimura, Takuya Takagi, Xiaoliang Geng, Takeaki Uno · 2014
In this paper, we study the problem of finding maximal dura- tion ock patterns from trajectory data in dimension d = 2 or more, which is a class of spatio-temporal closed patterns introduced by (Gudmundsson and van Kreveld, 2006). The problem of the previous approaches to was the exponential dependency of the running time on the duration length k and the dimension d. Also, they may miss some portion of patterns. For the problem, we present polynomial delay and space mining algorithms that finds all maximal duration flock patterns with specified radius and more than one entities appearing in an input collection of n trajectories in O(dkn) time per pattern using O(dm 2 ) extra space based on depth-first search, where m and k are the subset size and the length of a pattern to find, respectively. To the best of our knowledge, this is the first result on a polynomial delay and space algorithm for complete mining of all max- imal patterns in the class for every d ≥ 2. We also describe a speed-up technique using spatial-index. Finally, we present some experimental re- sults, where the improved version of proposed algorithms outperform the previous algorithm BFE (Vieira et al, 2009).