# A Distributed Execution Pipeline for Clustering Trajectories Based on a Fuzzy Similarity Relation
## 3 Background  
**Definition 1**. : _Let \(A\) be a lexical attribute (warm). The fuzzy set characterising this attribute is denoted \(A=\{\langle x,\mu_{A}(x)\rangle\mid x\in X,\mu_{A}\in[0,1]\}\). The \(\mu_{A}\) defines the degree of membership of a lexical variable to the set \(A\). Thus, each element of the universe of discourse \(X=\{x_{1},x_{2},...,x_{n}\}\) can be attributed to several sets with a varying membership degree [23]._  
**Definition 2**. : _A couple of crisp sets' elements can be related to each other via a relation. The relation is binary and can be formulated as \(R=\{\langle(x,y),\mu_{R}(x,y)\rangle\mid x\in X,y\in Y\}\). In case the relation is crisp the strength of the relationship \(\mu_{R}:(X,Y)\) equals 0 or 1. In contrast, a binary fuzzy relation has its membership degrees in \([0,1]\). In our study, we consider the latter relation._  
\(R\) _has the resolution form \(R=\bigcup\limits_{\alpha}R_{\alpha}\) with \(\alpha\in[0,1]\). \(R_{\alpha}\) is a crisp relation with_  
\[\mu_{R_{\alpha}}(x,y)=\left\{ \begin{array}{l}1\text{, if }\mu_{R}(x,y)\geq \alpha\\ 0\text{, otherwise}\end{array} \right.\]  
\(R\) _can be denoted a proximity relation if it is both reflexive and symmetric. In particular :_  
* _(Reflexivity):_ \(\forall x\mid X,\mu_{R}(x,x)=1\) _;_
* _(Symmetry):_ \(\forall x,y\mid X\times Y,\mu_{R}(x,y)=\mu_{R}(y,x)\) _;_  
_Additionally, if \(R\) respects transitivity, it can be refered to as a fuzzy similarity relation. Transitivity is defined as \(\mu_{R}(x,z)\geq max(T(\mu_{R}(x,y),\mu_{R}(y,z)))\). \(T\) is a \(t\)-norm defining the nature of the transitivity; several norms of this kind exist including :_  
* _(max-min transitivity):_ \(T(\mu_{1},\mu_{2})=min(\mu_{1},\mu_{2})\)_;_
* _(max-\(\Delta\) transitivity):_ \(T(\mu_{1},\mu_{2})=max(0,\mu_{1}+\mu_{2}-1)\)_;_
* _(max-prod transitivity):_ \(T(\mu_{1},\mu_{2})=\mu_{1}\bullet\mu_{2}\)_._  
_Moreover, \(\mathcal{R}_{\wedge}\subseteq\mathcal{R}_{\bullet}\subseteq\mathcal{R}_{\triangle}\) with \(\mathcal{R}_{\wedge},\mathcal{R}_{\bullet},\mathcal{R}_{\triangle}\) respectively form the set of max-min, max-prod and max-\(\triangle\) transitive relations [24]. In particular, the max-min transitivity yields a fuzzy similarity relation that characterizes each crisp relation in the resolution form as an equivalence relation. Different partition trees can be obtained for each \(\alpha\)-level from these equivalence relations [14]._  
**Definition 3**. : _The fuzzy similarity relation \(R\) can be extracted by achieving a series of compositions. A composition has the form \(R\circ R=\underset{y}{\max}(\underset{x,z}{T}(R(x,y),R(y,z))\). In our paper, we deploy both the semi-naive and smart algorithm for computing the transitive closure (please see the Section 4.1 for a precise implementation)._  
**Definition 4**. : _Trajectories can be mainly considered as a temporally ordered sequence and not forcibly related to space in this case they are considered metaphorical. Metaphorical trajectories describe the variations of an attribute over time. Decidedly in the case of an attribute \(a\), \(\text{Tr}_{a}=\{(a_{0},t_{0}),...,(a_{n},t_{n})\}\) with \(t_{i}\) as a timestamp. Another representation considers the variations of an attribute over abstract spatial regions instead of spatial coordinates, e.g., cities and countries. This representation is referred to as naive and \(\text{Tr}_{a}=\{(a_{0},t_{0},C_{0}),...,(a_{n},t_{n},C_{n})\}\) with \(C_{i}\) the country or region code. In contrast, raw trajectories consider spatial coordinates and describe the spatio-temporal profile of a moving object. Each trajectory has the form \(\text{Tr}_{(object_{id},trajectory_{id})}=\{(long_{0},lat_{0},t_{0})...(long_{n}, lat_{n},t_{n})\}\) with \(lat_{i}\) and \(long_{i}\) respectively denoting the latitude and longitude degrees [25]. In our study, we handle the raw trajectories of the Geolife project's GPS trajectory dataset [1; 2; 3]._  
**Definition 5**.