## 3 Materials and Methods
### Problem Definition  
A spatio-temporal database, whose records are moving objects with geolocation data attributes in two-dimensional space \(\mathcal{D}\), is assumed. In real world examples objects move arbitrarily which oppose to fixed velocity assumption that some works suppose. Hence, it is considered that the objects velocity is low with values between a minimal and a maximal, i.e., \(u\in[u_{min},u_{max}]\). In addition to, we consider low data sampling rate, since applying high data sampling rate it would be difficult to apply linear interpolation between sampled points, thus, the adopted dual methods should be redesigned adopting appropriate curve fitting methods. As a result, the velocity calculated from two consecutive way points could not represent the real velocity well and Euclidean distance would not work. In the following, an overview of the studying problem definitions along with notations is presented. **Definition 1**. : _The trajectory of a moving object is assumed to be a continuous piece-wise linear function, which maps the temporal dimension to the two-dimensional Euclidean space, connecting a sequence of points \((x_{1},y_{1},t_{1}),(x_{2},y_{2},t_{2}),\ldots,(x_{L},y_{L},t_{L})\) for \(t_{1}<t_{2}<\ldots<t_{L}\)._  
Such a representation entails that the \(n\)-th object position at time \(t_{i}\) is \(pos_{n}^{t_{i}}=(x_{i},y_{i})\) for \(n=1,2,\ldots,N\), and that during each time interval \((t_{i},t_{i+1})\), the object moves along a straight line from \((x_{i},y_{i})\) to \((x_{i+1},y_{i+1})\) with a constant velocity (amplitude and direction). To ensure an efficient storage and handling of the queries, the expected position of the object at any time \(t\in(t_{i},t_{i+1})\), where \(1\leq i\leq L-1\), is obtained by a linear interpolation between \((x_{i},y_{i})\) and \((x_{i+1},y_{i+1})\). In this way, a number of additional features can be extracted, such as velocity \(u\), angle direction \(\theta\), Hough-\(X\) and/or Hough-\(Y\) transformation of \((x,y)\)[9]. **Definition 2**. : _A moving object trajectory (spatio-temporal) snapshot is defined as the location data of that object in a specific timestamp; thus, a single trajectory is stored as a collection of location snapshots denoted as \(\{pos_{n}^{t_{i}}\}_{i=1}^{L}\)._  
**Definition 3**. : _Snapshot Distance: Given two objects \(o_{1}\) and \(o_{2}\) with location snapshots \(pos_{1}^{t_{i}}\) and \(pos_{2}^{t_{i}}\) respectively, the \(l2-norm\) distance (Euclidean) (Without loss of generality, both other distance measures can be considered, such as the Manhattan distance (\(l_{1}-norm\)), as well as the maximum distance (\(l_{\infty}-norm\))) between \(o_{1}\) and \(o_{2}\) in \(\mathcal{D}\) at timestamp \(t_{i}\) is computed as_  
\[dist_{o_{1},o_{2}}^{t_{i}}=\sqrt{\sum_{j=1}^{D}(pos_{1}^{t_{i}}[j]-pos_{2}^{t_ {i}}[j])^{2}}. \tag{1}\]  
The distance between two objects in our model is represented in Euclidean distance. The spatial \(k\)-NN queries are considered as one of the most common search problems that will be employed in our study. Generally, given a spatial region, a \(k\)-NN query on spatial data identifies all the spatial points that lie inside this region. For spatio-temporal \(k\)-NN queries, a time interval is also given, where the timestamps of the resulting trajectories in that region need to also fall in that time interval. A spatial \(k\)-NN query takes as input a query center point along with a set of spatial objects location data in order to find the \(k\) nearest neighbors around the center point. **Definition 4**. : \(k\)_-NN: Given a moving object \(m_{o}\), a dataset \(O\) and an integer \(k\), the \(k\) nearest neighbors of \(m_{o}\) from \(O\), denoted as \(kNN(m_{o},O)\), is a set of \(k\) objects from \(O\) that \(\forall o\in kNN(m_{o},O),\forall s\in O-kNN(m_{o},O),dist_{o,m_{o}}\leq dist_{s,m_{o}}\)._  
**Definition 5**.