# A Distributed Execution Pipeline for Clustering Trajectories Based on a Fuzzy Similarity Relation
## 1 Introduction  
In our time, billions of events are generated by location-aware devices in a matter of seconds. The extracted events' knowledge can be leveraged to increase economic gain, reinforce security and support decision making. In particular, the pattern analysis of the moving object trajectories can make it possible to understand or predict behaviour. Hence, cluster analysis has been quite indispensable. Still, the real-time, fuzzy, heavy nature of events has been a burden for conventional clustering approaches. Consequently, researchers have taken interest in fields like big data, online clustering and fuzzy logic.  
Big data technologies often refer to notions like concurrency, distribution, parallelism and stream processing. Mainly, deployed in a cluster environment where the memory and storage can be shared by the cluster's nodes. The nodes can be located in the same location or distributed among regions with a possible peer-to-peer or master-slave connection strategy. High Availability, mass storage, mass computing and fault tolerance are primarily featured by big data ecosystems. In this study, we take interest in leveraging the functionalities of Spark ([[https://spark.apache.org/](https://spark.apache.org/)]([https://spark.apache.org/](https://spark.apache.org/))) into clusteringtrajectories. The choice is supported by the fast computing nature of spark explained by its use of the Random Access Memory (RAM). In particular, we analyse the Geolife project's GPS trajectory dataset [1; 2; 3]. The dataset is stored in HDFS and an entire pipeline for reading, manipulating and defining clusters is being detailed in this paper. Clustering is done by computing the max-min transitive closure of a fuzzy proximity relation. Several trajectory similarity indices exist on the literature [4] and reasoning about which one is more accurate than the others is out of the scope of this paper. Consequently, for simplicity we consider the Longest Common Subsequence's (LCCS) length [5]. In the process, we have included the max-min, max-delta and max-product transitivity. An option of both the smart [6] and semi-naive [7] algorithms is deployed for computing the transitive closure. The system is implemented in Scala; hence, futures, traits, objects and higher-order functions are integrated to enrich the system's model. The pipeline's activity diagrams, system's class diagrams and different algorithms are detailed. Furthermore, we have encountered an issue related to unbalanced workloads; thus, we propose a new partitioning logic that considers the complexity of data and equally partitions it across the executors. By resolving the load balancing issue, the computation time was significantly reduced. After defining the clusters, we persist the results in a MongoDB ([[https://www.mongodb.com/](https://www.mongodb.com/)]([https://www.mongodb.com/](https://www.mongodb.com/))) collection by leveraging the reactive Mongodb driver ([[http://reactiveongo.org/](http://reactiveongo.org/)]([http://reactiveongo.org/](http://reactiveongo.org/))) known for its asynchronous nature. This final step can be extended to infer knowledge and analysed for understanding Spark's behaviour in the asynchronous boundaries. To the best of our knowledge, this is the first research giving a detailed implementation of the raw trajectories clustering process in Spark by leveraging a fuzzy similarity relation, analysing the performance of repartitioning tasks and providing a new partitioning strategy for handling trajectory data skewness and empirical proof of its efficiency.  
The rest of this paper involves three sections: Section 2 discusses the existing literature; Section 3 yields a background over fuzzy logic, fuzzy relations, LCCS problem and the transitive closure; Section 4 provides the different algorithms, class and activity diagrams; Section 5 provides the evaluation of the different partitioning stages; Section 6 concludes our paper and highlights future work.