An Improved Base Algorithm for Online Discovery of Flock Patterns in Trajectories

Abstract

The high availability, cost, and usage of location-aware devices have increased the interest in the research of spatiotemporal patterns. The main goal in studying such patterns is to discover spatial relationships over time between moving objects. Recent articles have proposed a wide variety of such patterns, among them is the flock pattern. This pattern is defined as a set of moving objects with minimum size that stay together within a maximum distance for a continuous period of time. Typical application examples are monitoring and surveillance, which rely on efficiently identifying groups of suspicious people/vehicles in large spatiotemporal streaming data. Previous works proposed polynomial-time algorithms to the flock pattern problem with fixed time duration. In this article, we propose a new online method, called PSI, which is an improved base method to discover flock patterns that applies computational geometry techniques (e.g., plane sweeping) along with binary signatures and inverted indexes. In summary, plane sweeping speeds up the detection of candidate groups in a particular timestamp, binary signatures allow saving costly set intersection operations, and inverted indexes are employed to quickly compare candidate disks across timestamps. Using a variety of real-world datasets and a large synthetic one we show that our proposed methods are efficient compared to state-of-the-art solution. In our experimental evaluation our proposed method achieved up to 69 times speedup compared to the previous solution.