A Trajectory Segmentation Algorithm Based on Interpolation-based Change Detection Strategies Mohammad Etemad Amílcar Soares Arazoo Hoseyni Institute for Big Data Analytics Institute for Big Data Analytics Institute for Big Data Analytics Halifax, NS Halifax, NS Halifax, NS etemad@dal.ca amilcar.soares@dal.ca a.hoseyni@dal.ca Jordan Rose Stan Matwin Institute for Big Data Analytics Institute for Big Data Analytics Halifax, NS Polish Academy of Sciences jordanrose@dal.ca Halifax, NS stan@cs.dal.ca ABSTRACT Finally, semi-supervised methods use a combination of both la- Trajectory mining is a research field which aims to provide fun- beled and unlabeled data as a criterion. Although efforts to create damental insights into decision-making tasks related to moving labeled trajectory datasets [8, 23] can be found in literature, the objects. One of the fundamental pre-processing steps for trajec- majority of them do not contain such information. Therefore, tory mining is its segmentation, where a raw trajectory is divided this work focuses on the development of unsupervised methods into several meaningful consecutive sub-sequences. In this work, for trajectory segmentation. we propose an unsupervised trajectory segmentation algorithm Since trajectory data is usually large and has all the charac- named Octal Window Segmentation (OWS) that is based on the teristics of Big Data, i.e., volume, velocity, variety, veracity, and processing an error signal generated by measuring the deviation value, presenting a fast and accurate segmentation method is of of a middle point of an octal window. The algorithm we propose prime importance. In this research, we investigate the topic of tra- is flexible and can be applied to different domains by selecting jectory segmentation and propose an unsupervised segmentation an appropriate interpolation kernel. We examined our algorithm method that can generate high-quality segments. The intuition on two datasets from different domains. The experiments show behind our approach is that when a moving object changes its that the proposed algorithm achieved more than 93% of a cross- behavior, this shift may be detected using only its geolocation validated harmonic mean of purity and coverage for two different over time. Unlike, previous methods that uses speed variations datasets. We also show that statistically significantly higher re- [14], direction variation [15], or a combination of many features sults were obtained by OWS when compared with a baseline for [8, 9, 11, 13, 16], this work focuses on finding these changes in unsupervised trajectory segmentation. behavior only from the object’s coordinates using interpolation methods to generate an error signal. This error signal is then used as a criterion to split the trajectories into sub-trajectories. 1 INTRODUCTION Our method can be customized to a domain by using different Processing traces of people, vehicles, vessels, and animals have kernel interpolation methods. The contributions of this paper been the focus of attention in the academic and industry sectors. are (i) the proposal of an unsupervised trajectory segmentation These traces of moving objects are called trajectory data and method named OWS, (ii) a comparison of OWS and a baseline can be informally defined as a consecutive sequence of the geo- regarding performance and execution time, and (iii) a compar- locations of a moving object. Transportation mode detection [6], ison of different kernel interpolations for datasets of different fishing detection [4], tourism [7], environmental science [18], and domains. traffic dynamics [2, 5, 20], are few examples of domains where The rest of this paper is organized as follows. We review the trajectory mining methods can be applied. algorithms for trajectory segmentation and interpolation in Sec- One of the fundamental trajectory mining tasks is segmenta- tion 2. In Section 3, the definitions used through this paper, and tion, i.e., split raw trajectories into sub-trajectories. Trajectory the OWS algorithm are detailed. The experiments (e.g., metrics, segmentation is a fundamental task since the method influences dataset, hyperparameter tuning, and results) and its analysis the features representing each trajectory. An accurate segmen- are detailed in Section 4. Finally, Section 5 provides conclusions tation method may provide higher quality features that better obtained from this work and future work that may be conducted. represent the moving object behavior. The segmentation task is therefore based on methods capable of distinguishing the homo- geneous or similar parts of a trajectory based on some criteria. Three cases can be distinguished: supervised, unsupervised, and 2 RELATED WORK semi-supervised trajectory segmentation. Unsupervised methods Trajectory segmentation methods such as TRACLUS [10], W- use only the raw trajectory as input, while supervised methods KMeans [11], SMOT [1], CB-SMoT [14], GRASP-UTS [16], and use labels available in a training data to extract some knowledge RGRASP-SemTS [9] have been proposed to segment trajectory and use this knowledge as criteria to generate the sub-trajectories. data. These methods are briefly reviewed in Section 2.1. Since the © 2019 Copyright held by the owner/author(s). Published in Proceedings of the proposed method can be customized for a domain by selecting Published in the Workshop Proceedings of the EDBT/ICDT 2019 Joint Conference different interpolation methods as kernel, we reviewed some on CEUR-WS.org, March 26, 2019: Distribution of this paper is permitted under the terms of the Creative Commons major interpolation methods in Section 2.2. license CC-by-nc-nd 4.0. 2.1 Trajectory segmentation 3.1 Definitions Trajectory segmentation methods can be divided into three cate- A trajectory point (pi ) is defined as pi = (x i , yi , ti ), where x i gories regarding the input data of the algorithm: (i) unsupervised, is longitude, yi is latitude, and ti (ti < ti+1 ) is the capturing (ii) supervised, and (iii) semi-supervised. time of the moving object. A raw trajectory (τn ), is a sequence of Unsupervised methods use only raw trajectory data as input trajectory points captured through time, τ = (pi , pi+1 , .., pn ), pi ∈ and compute a set of features from it. This family of methods τn and i ≤ n. considers the similarity among features in the neighborhood of a A segment or sub-trajectory is a subsequence of a raw trajectory sequence to create a set of sub-trajectories [11, 16, 21]. Supervised generated by splitting it into two or more sub-sequences. For methods use labels available in training data to extract some example, if we have one split point, k, and τn is a raw trajectory knowledge and use it as criteria to generate the sub-trajectories then s 1 = (pi , pi+1 , ..., pk ) and s 2 = (pk +1 , pk+2 , ..., pn ) are two [3, 14, 23]. Finally, semi-supervised methods use a combination sub-trajectories generated from τn . The process of generating of both labeled and unlabeled data as a criterion. The RGRASP- sub-trajectories from a raw trajectory is called segmentation. SemTS is an example of such method [9]. An octal window (Sow ) is a sub-trajectory with seven trajectory A trajectory segmentation can use a cost function or clustering points, in which new trajectory points are created using inter- methods to create sub-trajectories. GRASP-UTS, RGRASP-SemTS, polation techniques. We define Sow = (p1 , p2 , p3 , p4 , p5 , p6 , p7 ) so and W-KMeans are examples of cost function based methods, that pi is time-ordered. The indexes are relative for each window while TRACLUS, SM0T, and CB-SMoT are examples of clustering so that it can slide over a raw trajectory and represents different based methods. windows. A quantitative comparison between some of the aforemen- The decision of using seven trajectory points on a window tioned methods is given in [16]. They reported higher perfor- was motivated by the fact that it is necessary to use at least three mance for GRASP-UTS in comparison to W-KMeans, and CB- points to interpolate (predict) a trajectory point preceding or fol- SMoT. The highest segmentation performance shown in [16] was lowing them. Calculating acceleration in kinematic interpolation a purity of 91.37% and coverage of 83.00% on the fishing vessels requires at least three points. Since we use interpolation going dataset, and purity of 90.57% and coverage of 83.47% on the hur- both forward and backward, we have used three points in the ricanes dataset ( to be detailed in Section 4.1). In this work, we beginning of the window to predict forward the position of the repeated the experiments in the same environment and showed fourth point, and three points in the end of the window to predict that our proposed method obtained better results when compared backward another fourth point, expected to be very close to the to GRASP-UTS. result of the forward interpolation (see details in Section 3.2). We then use these two interpolated positions to create a midpoint and calculate its geographical distance from p4 . Since we have 2.2 Interpolation two sets of four points each, the minimum number of required Sometimes it is necessary to resample the frequency of trajec- trajectory points is seven points. Increasing the length of octal tory data due to signal loss. Calculating the geolocation for a window can possibly improve the results; however, the objective time-stamp that the geolocation is missing called interpolation. of this work is to use minimal possible memory. We use the term Different methods such as linear, random walk, bézier curve, current octal window to refer to the window being processed by catmull-row, and kinematic path have been introduced to calcu- our procedure at a given moment. After processing a window, we late the geo-location of these missing points. An interpolation slide the trajectory by one point and process the next window. method can be useful for one domain and useless for others. For example, random walk interpolation can be useful to interpolate wild animal behavior [17]. The bézier curve interpolation can be 3.2 Octal Window Segmentation Algorithm useful for moving objects in fluid environments [19]. The hermite The intuition behind our algorithm is that when a moving ob- and spline interpolation can be useful for AIS data(trajectories ject changes from one behavior to another, this can be captured of vessels) [22] and kinematic interpolation is useful for trans- directly from its geolocation. To achieve an estimated position, portation [12] or fast moving objects. Linear interpolation is where the moving object is supposed to be if its behavior does not the simplest, popular interpolation method. In this method, the change, we use interpolation methods. After, we compare the real missing location calculated so that it is sitting on a straight line position of the moving object with the estimated one, creating between two available points. Cubic and Kinematic methods cal- an error signal. By evaluating this error signal, it is possible to culate the speed and acceleration of the moving object in each estimate if the moving object changed its behavior on a region point of the octal window to interpolate the missing position. and use this information to create sub-trajectories. We implemented random walk, kinematic, cubic, and linear in- The first procedure that composes OWS unsupervised trajec- terpolation to utilize as a kernel for the proposed segmentation tory segmentation algorithm is detailed in Algorithm 1. This algorithm with the objective of exploring their results into differ- procedure creates an error signal by sliding the octal window ent trajectory datasets. over a raw trajectory τn . The procedure starts with an array of Error signals (E) in line 1. In line 2, the empty signal set [0, 0, 0] is added to the list 3 THE TRAJECTORY SEGMENTATION and represents the error for the first three points from the raw METHOD trajectory. The algorithm explores all the octal windows from In this section, we detail our novel algorithm for unsupervised lines 3 to 10 as follows. First, the actual octal window is created trajectory segmentation named Octal Window Segmentation (line 4). The forward interpolation is calculated in line 5. In this (OWS). We first introduce the definitions used to describe the method, we assume that pi in the current octal window is missing algorithm (Section 3.1). After, we detail OWS algorithm step by and will be interpolated using points p1 , p2 , p3 . The interpolated step in Section 3.2. point at time t i = t 3 + t5 −t 2 is called p . After, the backward 3 F Algorithm 1 Generate Error Signal Require: τn - the raw trajectory Figure 2: An example of an error signal calculation for an 1: E ←− {} octal sliding window Sow . 2: E.append([0, 0, 0]) 3: for (i = 3; i < n − 3; i + +) do 4: Create octal window Sow = (pi−3 , ..., pi+3 ) 5: pF ← − interpolate forward Sow 6: pB ← − interpolate backward Sow 7: pC ← − extract midpoint from P F and P B 8: ϵi ←− Haversine(pi , pC ) 9: E.append(ϵi ) 10: end for 11: E.append([0, 0, 0]) 12: return E interpolation method is calculated (line 6). In this method, it is also assumed that pi in the current octal window is missing. However, we reverse the order of points so that points p7 , p6 , p5 are used to Algorithm 2 Octal Window Segmentation interpolate the point pi at time t i = t 5 − t5 −t 3 2 and the procedure calls it p . In line 7, we use p and p geolocations to calculate B F B Require: ϵ min. error value to split a trajectory a midpoint (pC ). The error signal ϵi is finally computed in line 8, 1: E ←− Generate Error Signal (τn ) and it is obtained by calculating the haversine distance between 2: f irst ←−0 pi and pC . 3: q ←− [(f irst, n)] 4: p ←−∅ 5: while q , ∅ do Figure 1: An example of an error signal calculation for an 6: t ← q.pop() octal sliding window Sow . 7: curr ← E[t[0] : t[1]] 8: m ← max(curr ) 9: if m > ϵ then 10: idx ← index(curr == m) 11: if len(idx) == 1 then 12: q.append((t[0], t[0] + idx[0])) 13: q.append((t[0] + idx[0] + 1, t[1])) 14: else 15: ixx ← дroup index(idx) 16: for all д ∈ ixx do 17: q.append((f irst, ixx[д])) 18: f irst = ixx[д] 19: end for 20: q.append((f irst, t[1])) 21: end if 22: else 23: p.append(t) Figure 1 shows the p B and p F interpolated positions as red 24: end if points, pi as a green point and pC as a yellow point. In the ex- 25: end while ample of Figure 1, the haversine distance from the estimated 26: return p position pC to the real position pi is visible. This may indicate that the moving object behavior has changed at position pi . In Figure 2, an example of an error signal generated by Algo- creating the error signal E that is the output of the procedure in rithm 1 is shown. A raw trajectory with around 150 trajectory Algorithm 1. In lines 2 and 3, the algorithm initializes the f irst points was used in this example. As can be seen in Figure 2, there variable with a 0 value which represents the starting index of the are several trajectory points (e.g., around trajectory point 95, or trajectory and creating the first tuple (f irst, n) that represents around trajectory point 123) along the raw trajectory where the the entire trajectory and adding it to a list q. In line 4, the final estimated positions were far from the actual reported positions variable p with all the partitioning positioning tuples is declared by the moving object. as an empty. While the list q is not empty, lines 6 to 24 are The OWS algorithm is detailed in Algorithm 2 which receives executed. First, this algorithms get the first element of the list t as input a single ϵ value. The intuition of how this algorithm (line 6), which in the first run is the full trajectory, creates a list works is that segments are created in partitioning positions where curr with all the error values from E (line 7), and gets its maximal the error values from E are higher than the ϵ value and these error value m (line 8). If this maximal error value is greater than partitioning positions are created as a list of tuples with the the threshold, the index of m is retrieved, and two new tuples indexes of where segments start and end. Algorithm 2 starts are created if there is a single position with value m (lines 11 to 13). The new tuples are stored in q and are analyzed in the next estimating the input parameters values of both algorithms, and iteration of the algorithm, which will look for other error values the remaining nine to verify the algorithm’s performance in terms higher than the ϵ threshold. If there is more than one partitioning of the harmonic mean of average purity and coverage. The same position with a value equal to m (lines 14 to 21), tuples are created process was repeated for every single subset as the set for input in every single position that satisfies this criterion. This procedure parameters value estimation, and validation in the remaining will run until all the tuples with partitioning positions are created subsets. As a result, ten different values of the harmonic mean of where error values are greater than the error threshold ϵ. In the average purity and coverage were found in our experiments. last step, i.e. if m ≤ ϵ, tuple t is appended to the final list p. The input parameter values estimation for GRASP-UTS was done by a grid search with all combinations of values reported in 4 EXPERIMENTS [16]. The decision of the best input parameters combination was guided by the best cost function value achieved by an algorithm This section details the metrics and datasets (Section 4.1) and configuration, in the same way, reported in [16]. algorithms parameter selection (Section 4.2) procedure. Finally, For the OWS segmentation algorithm, the ϵ value was found the interpolation methods analysis obtained with the OWS algo- using the following steps. First, the total error signal E was gen- rithms detailed in Section 4.3 and Section 4.4 shows a comparison erated for the one subset for parameters estimation. After, the between our OWS strategy and a baseline segmentation algo- harmonic mean of the purity and coverage was calculated by rithm. running OWS and using values of percentiles (P) from E. We tested the percentiles values for every ϵ ∈ E from 99 to 90 4.1 Metrics and datasets (P = [P99 , P98 , P97 , P 96 , P95 , P94 , P93 , P92 , P 91 , P90 ]. The percentile Since our method is classified as an unsupervised method, cluster- that produced the highest harmonic mean was chosen to be used ing metrics such as purity, coverage, and the harmonic mean of as the ϵ value and was used to estimate the harmonic mean in purity and coverage are proper evaluation metrics. In this work, the remaining nine subsets. we have used the metrics named average purity and average cov- erage. They were first introduced in the context of trajectory 4.3 OWS interpolation methods evaluation segmentation in the work of [16]. These two metrics were de- In the first experiment, we tested the kinematic, linear, random signed to be orthogonal, i.e., when one tends to increase, the other walk, and cubic interpolation methods in OWS for the hurricanes tends to decrease. Therefore, we defined the harmonic mean of and fishing datasets. average purity (P) and average coverage (C), harmonic mean (H), The results on fishing dataset show that random walk interpo- H = 2∗P ∗C , as the primary metric for our analysis and to simplify lation produces the highest harmonic mean. Since we do not have P +C the plots and comparison of the segmentation algorithms. enough samples (10 harmonic mean values for every segmenta- The segment purity in a segment is defined as follows. Assum- tion algorithm) to verify if the outcomes are normally distributed, ing the set of all target labels in a segment is L with k trajectory we have used the Mann Whitney U test to verify if the difference points. The majority label, pd ∈ L, is the label of majority tra- in the results is significantly different. If P was lower than 0.05, jectory points in the segment and the number of occurrence of we rejected the hypothesis that the observed median values came p pd is p. Therefore, the purity of a segment is k . The average of from the same distribution, so there are statistical differences. A purity values for all segments generated by a trajectory segmen- Mann Whitney U test indicated that the random walk interpola- tation algorithm is called average purity, P. The coveraдe of a tion kernel produces statistically significant higher median (M segment can be calculated using a segment identifier (sid ) from = 93.68) harmonic mean for trajectory segmentation comparing the segments found by the segmentation algorithm. Assuming to kinematic (S = 11.0, P = 0.0018, M = 86.98), linear (S = 22.0, P σm is a segment that was supposed to be found by a segmenta- = 0.0188, M = 91.57), and cubic (S = 13.0, P = 0.0028, M = 91.61) tion algorithm, it is possible to verify for every segment found interpolation. We think that this result shows that the human by the algorithm the most frequent sid by sm id . The average for factor (i.e., the vessel’s captain) plays an essential role in detect- coverage of all generated segments is then called C. The more ing fishing activities and this is reflected in random movement over segmented a trajectory is, higher values of purity are ex- behaviors changes. pected to be found. However, lower values for coverage will be Table 1: Comparing OWS interpolation methods on the computed in the case of a large number of segments found by fishing dataset. the segmentation algorithm. The same conflicting result occurs if the trajectory is under segmented, i.e., the purity values tend to decrease, but the coverage tends to have a higher value. RW LIN KIN CUB Two datasets were selected for evaluation of OWS and the M 93.68 91.57 86.98 91.61 baseline named GRASP-UTS: (i) fishing (5190 points, 153 seg- σ 1.85 2.68 4.88 1.56 ments) and (ii) hurricane datasets (1990 points, 182 segments). The dataset was processed using the same conditions and features The results on the hurricanes dataset are detailed in Table adopted in the experiments of [16]. The objective was to achieve 2. The results show that kinematic interpolation produces the the best result reported by GRASP-UTS for the unsupervised highest harmonic mean. A Mann Whitney U test indicated that trajectory segmentation problem. the kinematic interpolation (M = 93.11) kernel produces statisti- cally significant higher median harmonic mean for octal window 4.2 Algorithms parameter selection segmentation comparing to random walk(S = 18.0, P = 0.0086, M In the experiments conducted in this work, ten different trajectory = 92.45), linear (S = 10.0, P = 0.0014, M = 90.71), and cubic (S = 9.0, subsets were created aiming to properly evaluate the performance P = 0.0011, M = 87.91) interpolation. We think that the kinematic of the segmentation algorithms. We have used one subset for interpolation worked better in this dataset because a high-speed moving objects tend to follow this strategy and also the sampling rate for this dataset is constant (e.g., every 6 hours). Table 2: Comparing OWS interpolation methods on the hurricanes dataset. RW LIN KIN CUB M 92.45 90.71 93.11 87.91 σ 1.24 1.12 2.53 4.22 4.4 Comparison with a baseline In this section, we compare the algorithms for unsupervised tra- jectory segmentation named OWS and GRASP-UTS. Figure 3 (a) shows a violin chart for the results of OWS segmentation on the Figure 4: comparing results of OWS against GRASP-UTS fishing dataset in blue (left) and the GRASP-UTS in green (right) on Hurricanes dataset for all subsets and interpolation methods. The random walk inter- polation shows visible improvements against the GRASP-UTS, as well as all the other interpolation kernels. Furthermore, a Mann the trajectory data into sub-trajectories. The proposed model Whitney U test between the GRASP-UTS and the random walk is flexible to different domains by adjusting the interpolation interpolation kernel on fishing dataset shows that OWS produces methods. The experimental results show that the kinematic in- a statistically significant higher median for harmonic mean than terpolation is more suitable for the hurricane dataset, while the the GRASP-UTS. random walk interpolation was the best choice for segmenting The Figure 3 (b) shows the results of the OWS segmenta- the fishing dataset. OWS produces higher quality segmentation tion on hurricane dataset with blue (left) and the GRASP-UTS than the state-of-the-art segmentation algorithm, GRASP-UTS. with green (right). Even though the GRASP-UTS took advantage We compare our proposed model against GRASP-UTS, and the re- of using wind speed as a feature, the kinematic interpolation sults show that our algorithm achieved a statistically significant shows a considerable improvement against the GRASP-UTS. The higher harmonic mean of purity and coverage for the hurricane other interpolation methods also show competitive results with and fishing datasets. Furthermore, OWS does not need any extra GRASP-UTS. Another Mann Whitney U test done between the knowledge than the raw trajectory, while GRASP-UTS needs GRASP-UTS and the kinematic interpolation kernel on hurri- trajectory features such as speed, direction variation, etc. cane dataset shows that OWS produces a statistically significant This work can be extended in several directions. First, we in- higher median for harmonic mean than the GRASP-UTS. tend to expand the quantitative comparison of OWS with other methods like WK-Means and CB-SMOT and use other trajectory datasets like Geolife [24]. We also intend to evaluate the possibil- ity of other interpolation methods and the effects of increasing the window size used to create the error signal. REFERENCES [1] Luis Otavio Alvares, Vania Bogorny, Bart Kuijpers, Jose Antonio Fernandes de Macedo, Bart Moelans, and Alejandro Vaisman. 2007. A Model for Enrich- ing Trajectories with Semantic Geographical Information. In Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems (GIS ’07). ACM, New York, NY, USA, Article 22, 8 pages. https://doi.org/10.1145/1341012.1341041 [2] Pablo Samuel Castro, Daqing Zhang, Chao Chen, Shijian Li, and Gang Pan. 2013. From taxi GPS traces to social and community dynamics: A survey. ACM Computing Surveys (CSUR) 46, 2 (2013), 17. [3] Sina Dabiri and Kevin Heaslip. 2018. Inferring transportation modes from GPS trajectories using a convolutional neural network. Transportation Research Part C: Emerging Technologies 86 (2018), 360–371. [4] Erico N de Souza, Kristina Boerder, Stan Matwin, and Boris Worm. 2016. Improving fishing pattern detection from satellite AIS using data mining and machine learning. PloS one 11, 7 (2016), e0158248. Figure 3: Comparing results of OWS against GRASP-UTS [5] Renata Dividino, Amilcar Soares, Stan Matwin, Anthony W Isenor, Sean on Fishing dataset Webb, and Matthew Brousseau. 2018. Semantic Integration of Real-Time Heterogeneous Data Streams for Ocean-related Decision Making. In Big Data and Artificial Intelligence for Military Decision Making. STO. https://doi.org/ 10.14339/STO-MP-IST-160-S1-3-PDF 5 CONCLUSION [6] Mohammad Etemad, Amílcar Soares Júnior, and Stan Matwin. 2018. Predicting Transportation Modes of GPS Trajectories using Feature Engineering and In this work, we proposed an unsupervised trajectory segmenta- Noise Removal. In Advances in Artificial Intelligence: 31st Canadian Conference on Artificial Intelligence, Canadian AI 2018, Toronto, ON, Canada, May 8–11, tion algorithm named Octal Window Segmentation (OWS) that 2018, Proceedings 31. Springer, 259–264. segments trajectory data using interpolation methods to generate [7] Shanshan Feng, Gao Cong, Bo An, and Yeow Meng Chee. 2017. POI2Vec: a geolocation error signal from where it was supposed to be. This Geographical Latent Representation for Predicting Future Visitors.. In AAAI. 102–108. error signal represents possible partitioning positions where a [8] Amílcar Soares Júnior, Chiara Renso, and Stan Matwin. 2017. ANALYTiC: moving object changed its behavior, and it is used to segment An Active Learning System for Trajectory Classification. IEEE Computer Graphics and Applications 37, 5 (2017), 28–39. https://doi.org/10.1109/MCG. 2017.3621221 [9] Amílcar Soares Júnior, Valéria Times, Chiara Renso, Stan Matwin, and Lucıdio A. F. Cabral. 2018. A semi-supervised approach for the semantic segmen- tation of trajectories. In 19th IEEE International Conference on Mobile Data Management. [10] Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang. 2007. Trajectory clustering: a partition-and-group framework. In Proceedings of the 2007 ACM SIGMOD international conference on Management of data. ACM, 593–604. [11] Luis A. Leiva and Enrique Vidal. 2013. Warped K-Means: An algorithm to cluster sequentially-distributed data. Information Sciences 237 (2013), 196 – 210. https://doi.org/10.1016/j.ins.2013.02.042 Prediction, Control and Diagnosis using Advanced Neural Computations. [12] Jed A Long. 2016. Kinematic interpolation of movement data. International Journal of Geographical Information Science 30, 5 (2016), 854–868. [13] B. N. Moreno, A. Soares Júnior, V. C. Times, P. Tedesco, and Stan Matwin. 2014. Weka-SAT: A Hierarchical Context-Based Inference Engine to Enrich Trajec- tories with Semantics. In Advances in Artificial Intelligence. Springer Interna- tional Publishing, Cham, 333–338. https://doi.org/10.1007/978-3-319-06483-3_ 34 [14] Andrey Tietbohl Palma, Vania Bogorny, Bart Kuijpers, and Luis Otavio Alvares. 2008. A Clustering-based Approach for Discovering Interesting Places in Trajectories. In Proceedings of the 2008 ACM Symposium on Applied Computing (SAC ’08). ACM, New York, NY, USA, 863–868. https://doi.org/10.1145/1363686. 1363886 [15] Jose Antonio MR Rocha, Valéria C Times, Gabriel Oliveira, Luis O Alvares, and Vania Bogorny. 2010. DB-SMoT: A direction-based spatio-temporal clustering method. In Intelligent systems (IS), 2010 5th IEEE international conference. IEEE, 114–119. [16] A. Soares Júnior, B. N. Moreno, V. C. Times, S. Matwin, and L. A. F. Cabral. 2015. GRASP-UTS: an algorithm for unsupervised trajectory segmentation. International Journal of Geographical Information Science 29, 1 (2015), 46–68. [17] Georgios Technitis, Walied Othman, Kamran Safi, and Robert Weibel. 2015. From A to B, randomly: a point-to-point random trajectory generator for animal movement. International Journal of Geographical Information Science 29, 6 (2015), 912–934. [18] Tammy M Thompson, Sebastian Rausch, Rebecca K Saari, and Noelle E Selin. 2014. A systems approach to evaluating the air quality co-benefits of US carbon policies. Nature Climate Change 4, 10 (2014), 917. [19] Yann Tremblay, Scott A Shaffer, Shannon L Fowler, Carey E Kuhn, Birgitte I McDonald, Michael J Weise, Charle-André Bost, Henri Weimerskirch, Daniel E Crocker, Michael E Goebel, et al. 2006. Interpolation of animal tracking data in a fluid environment. Journal of Experimental Biology 209, 1 (2006), 128–140. [20] I. Varlamis, K. Tserpes, and C. Sardianos. 2018. Detecting Search and Rescue Missions from AIS Data. In 2018 IEEE 34th International Conference on Data Engineering Workshops (ICDEW). 60–65. https://doi.org/10.1109/ICDEW.2018. 00017 [21] Zhixian Yan, Nikos Giatrakos, Vangelis Katsikaros, Nikos Pelekis, and Yannis Theodoridis. 2011. SeTraStream: semantic-aware trajectory construction over streaming movement data. In International Symposium on Spatial and Temporal Databases. Springer, 367–385. [22] Daiyong Zhang, Jia Li, Qing Wu, Xinglong Liu, Xiumin Chu, and Wei He. 2017. Enhance the AIS data availability by screening and interpolation. In Transportation Information and Safety (ICTIS), 2017 4th International Conference on. IEEE, 981–986. [23] Yu Zheng, Hao Fu, X Xie, WY Ma, and Q Li. 2011. Geolife GPS trajectory dataset-User Guide. (2011). [24] Yu Zheng, Hao Fu, Xing Xie, Wei-Ying Ma, and Quannan Li. 2011. Geolife GPS trajectory dataset - User Guide. https://www.microsoft.com/en-us/research/ publication/geolife-gps-trajectory-dataset-user-guide/