A parallel GPU-based approach for reporting flock patterns

Abstract

Data analysis and knowledge discovery in trajectory databases is an emerging field with a growing number of applications such as managing traffic, planning tourism infrastructures or better understanding wildlife. In this paper, we study the problem of finding flock patterns in trajectory databases. A flock refers to a large enough subset of entities that move close to each other for, at least, a given time interval. We present parallel algorithms, to be run on a Graphics Processing Unit, for reporting three different variants of the flock pattern: (1) all maximal flocks, (2) the largest flock and (3) the longest flock. We also provide their complexity analysis together with experimental results showing the efficiency and scalability of our approach