intro.tex

\section{Introduction}
Technology advances in last past decades have triggered an explosion in the capture of spatio-temporal data.  The increase popularity of GPS devices and smart-phones together with the emerging of new disciplines such as the Internet of Things and Satellite/UAS high-resolution imagery have made possible to collect vast amount of data with a spatial and temporal component attached to them.

Together with this, the interest to extract valuable information from such large databases has also appeared.  Spatio-temporal queries about most popular places or frequent events are still useful, but more complex patterns are recently shown an increase of interest.  In particular, those what describe group behaviour of moving objects through significant periods of time.  Moving cluster \cite{kalnis_discovering_2005}, convoys \cite{jeung_discovery_2008}, flocks \cite{gudmundsson_computing_2006} and swarm patterns \cite{li_swarm:_2010} are new movement patterns which unveil how entities move together during a minimum time interval. 

Applications for this kind of information are diverse and interesting, in particular if they come in the way of trajectory datasets \cite{jeung_trajectory_2011, huang_mining_2015}. Case of studies range from transportation system management and urban planning \cite{di_lorenzo_allaboard:_2016} to Ecology \cite{la_sorte_convergence_2016}.  For instance, \cite{turdukulov_visual_2014} explore the finding of complex motion patterns to discover similarities between tropical cyclone paths.  Similarly, \cite{amor_persistence_2016} use eye trajectories to understand which strategies people use during a visual search. Also, \cite{holland_movements_1999} tracks the behavior of tiger sharks in the coasts of Hawaii in order to understand their migration patterns.

In particular, a moving flock pattern show how objects move close enough during a given time period.  Closeness is defined by a disk of a given radius where the entities must keep inside.  Given that the disk can be situated at any location, it is not a trivial problem.  In deed, \cite{gudmundsson_computing_2006} claims that find flock patterns where the same entities stay together during their duration is a NP-hard problem. \cite{vieira_2009} proposed the BFE algorithm which the first approach to be able to detect flock patterns in polynomial time.

Despite the fact that much more data become available, state-of-the-art techniques to mine complex movement patterns still depict poor performance for big spatial data problems.  This work presents a parallel algorithm to discover moving flock patterns in large trajectory databases.  It is thought that new trends in distributed in-memory frameworks for spatial operations could help to speed up the detection of this kind of patterns.

\section{Related work}
Recently increase use of location-aware devices (such as GPS, Smart phones and RFID tags) has allowed the collection of a vast amount of data with a spatial and temporal component linked to them.  Different studies have focused in discovering and analyzing this kind of collections \cite{leung_knowledge_2010, miller_geographic_2001}.  In this area, trajectory datasets have emerged as an interesting field where diverse kind of patterns can be identified \cite{zheng_computing_2011, vieira_spatio-temporal_2013}.  For instance, authors have proposed techniques to discover motion spatial patterns such as moving clusters \cite{kalnis_discovering_2005}, convoys \cite{jeung_discovery_2008} and flocks \cite{benkert_reporting_2008, gudmundsson_computing_2006}.  In particular, \cite{vieira_2009} proposed BFE (Basic Flock Evaluation), a novel algorithm to find moving flock patterns in polynomial time over large spatio-temporal datasets. 

A flock pattern is defined as a group of entities which move together for a defined lapse of time \cite{benkert_reporting_2008}.  Applications to this kind of patterns are rich and diverse.  For example, \cite{calderon_romero_mining_2011} finds moving flock patterns in iceberg trajectories to understand their movement behavior and how they related to changes in ocean's currents. 

The BFE algorithm presents an initial strategy in order to detect flock patterns.  In that, first it finds disks with a predefined diameter ($\varepsilon$) where moving entities could be close enough at a given time interval.  This is a costly operation due to the large number of points and intervals to be analyzed ($\mathcal{O}(2n^2)$ per time interval).  The technique uses a grid-based index and a stencil to speed up the process, but the complexity is still high.

\cite{calderon_romero_mining_2011} and \cite{turdukulov_visual_2014} use a frequent pattern mining approach to improve performance during the combination of disks between time intervals.  Similarly, \cite{tanaka_improved_2016} introduce the use of plane sweeping along with binary signatures and inverted indexes to speedup the same process.  However, the above-mentioned methods still keep the same strategy as BFE to find the disks at each interval.  

\cite{arimura_finding_2014} and \cite{geng_enumeration_2014} use depth-first algorithms to analyze the time intervals of each trajectory to report maximal duration flocks.  However, these techniques are not suitable to find patterns in an on-line fashion.

Given the high complexity of the task, it should not be surprising the use of parallelism to increase performance.  \cite{fort_parallel_2014} use extreme and intersection sets to report maximal, longest and largest flocks on the GPU with the limitations of its memory model.  

Indeed, despite the popularity of cluster computing frameworks (in particular whose supporting spatial capabilities \cite{eldawy_spatialhadoop:_2014, yu_demonstration_2016, pellechia_geomesa:_2015-1, xie_simba:_2016-1}) there are not significant advances in this area.  At the best of our knowledge, this work is the first to explore in-memory distributed systems towards the detection of moving flock patterns.