=Paper=
{{Paper
|id=Vol-1392/paper-16
|storemode=property
|title=Evaluating Distance Measures for Trajectories in the Mobile Setting
|pdfUrl=https://ceur-ws.org/Vol-1392/paper-16.pdf
|volume=Vol-1392
|dblpUrl=https://dblp.org/rec/conf/icml/LariosMKG15
}}
==Evaluating Distance Measures for Trajectories in the Mobile Setting==
Evaluating distance measures for trajectories in the mobile setting Nikolaos Larios NLARIOS @ DI . UOA . GR University of Athens Christos Mitatakis CMITATAKIS @ DI . UOA . GR University of Athens Vana Kalogeraki VANA @ AUEB . GR Athens University of Economics and Business Dimitrios Gunopulos DG @ DI . UOA . GR University of Athens Abstract computing and sensing platform. They are equipped with Mobile devices, such as smartphones allow us a variety of sensors such as GPS, cameras and accelerom- to use computationally expensive algorithms and eters. This gives birth to several unique opportunities for techniques. In this paper, we study algorithms in data collection and analysis such as finding trajectory sim- order to solve the problem of finding the most ilarities between trajectories generated and stored on dis- similar trajectory within a number of trajecto- tributed smartphones. We developed a framework that al- ries. We built a framework that enables the user lows users to find similar trajectories in a distributed en- to compare a trajectory Q with trajectories that vironment. Our framework requires the participation of a have been generated and stored on mobile de- number of users in order to find a solution of a query. In vices. The system returns to the user the most order to specify the way in which our framework works, similar trajectory based on the algorithm that has every query is assigned by a user of our system and it is ad- been selected. The algorithms for the measure- dressed to all the available users of our platform. The goal ment of the trajectory similarity have been imple- of our platform is to generate and store trajectory data on mented for mobile devices running Android OS. mobile devices (smartphones) and compare a query trace We evaluate our algorithms with real geospatial Q against the crowd of trajectories that is distributed on a data. large number of mobile devices. 1.1. Related Work 1. Introduction There are many methods and techniques related to search- The study of the similarity between trajectories is important ing for similar moving object trajectories. Some previous in a plethora of application domains (e.g. Traffic manage- methods were based on Euclidean distance space, but this ment, Video analysis, Molecular Design, Similarity of Me- is not suitable for road network space because is difficult teorological Phenomena etc.). More specifically, the tra- to apply the distance of Euclidean space to road network jectory similarity between moving objects is useful for ap- space. Other methods considered only spatial similarity plications in intelligent traffic systems, such as traffic navi- without considering temporal similarity to search for sim- gation and traffic prediction, both of which require mining ilar moving object trajectories. The methods that interest of past trajectories patterns, etc. The identification of simi- us the most are those that are used for measurement of the larities between moving objects is a challenging task, since spatio-temporal similarity between trajectories. Although not only their locations change but also because their speed in this work we do not consider the privacy issues that come and semantic features vary. Mobile devices and smart- up when data from users become available in the system, phones, in particular are rapidly emerging as a dominant there is work in the area that can be leveraged in a real system. In ”Select-Organize-Anonymize”(Giorgos Poulis, Proceedings of the 2 nd International Workshop on Mining Urban 2013), the authors find similar trajectories, by using Z- Data, Lille, France, 2015. Copyright c 2015 for this paper by its authors. Copying permitted for private and academic purposes. ordering and data projections on subtrajectories. Then they Nd Evaluating distance measures for trajectories in the mobile setting organize the selected trajectories into clusters which they difficult and expensive to accurately record an entire tra- anonymize after that. Another work that the researchers jectory. In spatio-temporal databases a trajectory is repre- propose a method to compare trajectories of moving ob- sented as a set of discrete samples of the positions of the ject is in ”Shapes based trajectory queries for moving ob- moving object of the form (x, y, t), i.e. a sequence of or- jects”.(Lin & Su, 2005) In this work, the writers intro- dered pairs (x, y), each characterized by a timestamp. As duce a new distance function and the evaluate the simi- described above our goal is to develop a distributed plat- larity measurement by using a grid representation to de- form for spatio-temporal similarity search between trajec- scribe trajectories. The most similar work is the paper tories generated and stored on distributed mobile devices. Crowdsourced Trace Similarity with Smartphones paper Specifically, given a query trajectory Q, we want to find (Zeinalipour-Yazti et al., 2013) where the writers try to any trajectories of the mobile devices using our platform solve efficiently the problem of comparing a query trace that follow a motion similar to Q. against a number of traces generated by smartphones. They The mobile application should be able to store locally the developed the SmartTrace+ framework which consists a trajectories that follow the mobile device, to receive a query distributed data storage model that trajectories are stored Q from another mobile device, through the server of the and top-K query processing algorithms that exploit trajec- platform, to evaluate if the mobile device has followed a tory similarity measures, elastic to spatial and temporal similar trajectory to Q and return its result back to the spe- noise. cific user through the server again. The platform should be able to compare a query trajectory Q that is submitted 1.2. Our Contributions by a user, simultaneously against a number of trajectories In this paper, we build a distributed mobile platform that that is stored on a large crowd of mobile devices. The most uses algorithms to search for trajectory similarity among a similar trajectory of every user with the query Q should number of trajectories that are stored in distributed mobile be received and managed from the server application en- devices. The trajectories which are stored have been col- suring the privacy of the users of the platform. Then the lected by monitoring the movement of the mobile devices. server finds the most similar trajectory within the results The users choose whether their movement will be recorded that have been collected and sends it back to the user who by the application. So our platform consists of two parts, submitted the query Q. Our approach exploits the fact that the one is where the users gather the trajectory data, so that nowadays, mobile devices have exceptional computational can be created a distributed database where the trajectories power and storing capabilities. Running the algorithms in are stored. a distributed mobile environment grants our platform the necessary performance and scalability in order to support a The second contribution of our platform is the mechanism great number of users and spatio-temporal data. Moreover, that given a query trajectory Q, we want to find any trajec- having the trajectories stored in the mobile devices the pri- tories of the mobile devices using our platform that follow a vacy of the users is protected. The definition of the term motion similar to Q. We initiate an experimental evaluation similarity between trajectories may vary between different of three different trajectory similarity measures, namely problem cases. For example in most cases the most sim- Dynamic Time Warping (DTW), Longest Common Subse- ilar trajectory should be determined by using not only the quence (LCSS), and Fréchet distance. Intuitively, Dynamic spatial shape of the trajectories but also their evolution in Time Warping (DTW) is the equivalent of the L2 distance time. In other cases the timing of the recording of the tra- when stretching of the trajectories is allowed since DTW jectory or the time intervals between points of interest that takes into account the individual differences of all matched are defined by the query may be of greater importance. points in the stretched sequences. Similarly, Longest Com- mon SubSequence (LCSS) can be thought of as the equiva- lent of L0 since it counts how many elements are the same. 3. System Overview Completing the analogy, the Fréchet distance is equivalent The system has two basic functionalities. The first one to Linf since it considers the maximum of the individual consists from the monitoring procedure, where the user differences of the matches in the stretched sequences. Here can monitor his movement. With this procedure, the users we perform an evaluation on their relative accuracy and trajectories are stored in the mobiles database creating performance. the necessary data. The second functionality contains the query submission from one user and the search for results, 2. Problem Definition using a selected algorithm, in the devices registered in the system. The architecture of our system is described by fig- Trajectory: Trajectory or trace of a moving object is a set ure 1. of consecutive positions in space as a function of time. Due to limitations on the acquisition and storing of data, is very N3 Evaluating distance measures for trajectories in the mobile setting 3.3. Data Storage Each device (mobile, tablet, etc.) can produce tuples of data through its sensors (eg GPS sensors, accelerometer, camera, microphone, etc.).The data that are stored in the mobile devices corresponds to the trajectories that have been performed by the device while the user have selected to record his movement. The form and amount of data depend on the application of the general form to iswhere: • The Id refers to the unique code that corresponds to the current trajectory that is recorded. Every time the user selects to monitor his movement, a new id is ini- tialized which define the recording. Figure 1. System’s architecture • The Latitude and Longitude determine the geographi- cal location of the tuple. • The Timestamp refers to the time of recording the cur- rent tuple. 3.1. System Components The goal of the system is to record and store efficient (in Examples of data form is: <1, 23.32134, 37.566643, 2014- time and resources) large amounts of data from N mobile 10-24 16:52:01> devices and support the communication between them and Every trajectory consists of a number of tuples like the ex- a main server in order to send queries on the data recorded ample above. Each tuple is recorded periodically every 2 and send their results. The way that data are stored must seconds. This period can be changed accordingly to our be defined, i.e. the structures that will be used in mobile preferences or the storage capabilities of the device. The devices and in the server for data storage. Our system con- trajectories that are recorded are stored in the devices inter- sists by the following: A main application server, which is nal memory. For the storage of data in the mobile devices responsible for receiving and forwarding queries between is used SQLite which is the default SQL database engine mobile devices using the application. Furthermore, it is re- for android powered devices. sponsible for the registration of mobile devices in the sys- tem. This application is hosted on an Ubuntu server. As mentioned above in the system will be registered N mo- 3.4. Querying component bile devices using the application’s mobile platform which The Android application we have developed is responsible is responsible for data recording, sending queries, receiv- for the collection and storing of trajectory data by record- ing and handling queries other devices and send data if the ing the movement of the mobile devices. Moreover, the query result was successful. algorithms that we use for the measurement of trajectory similarity have been implemented in the Android applica- 3.2. Users tion. The system consists of N users and those users participate A query Q when is formed by a user of our platform is in it through their devices (mobile, tablets, etc.). For the forwarded by the server to other registered mobile devices. efficient operation and acceptable results of the system, it When a mobile device receives a query it runs the selected requires a sufficient number of users. The more users reg- algorithm and searches the data that has been collected for ister to our platform the precision of the system will be in- the most similar trajectory, according to the selected algo- creased due to the available set of data for each geographic rithm. Let m1 , m2 , ...., mi denotes a set of i mobile de- area and time. User data are generated by the sensors of the vices. The server sends the query Q to this set of mobile devices and are stored locally on each device. Since users devices where Q is a sequence of points {p1 , p2 , ..., pj } that are not constantly connected to the system due to intermit- describes a trajectory. The application compare the trajec- tent connectivity for their mobile devices respectively no tory Q with each trajectory that is stored in the database of data will be offered to our system without their agreement. the device (e.g. {T1 , T2 , T3 , ..., Tk }), in order to find the NN Evaluating distance measures for trajectories in the mobile setting most similar one. All devices that have a result sends their where HEAD(S1) is the subsequence answers to the server. [S1,1 , S1,2 , ..., S1,m−1 ] and δ is an integer that con- trols the maximum distance in the time axis between 3.5. Server two matched elements and is a real number 0<ε<1 that controls the maximum distance that two elements are The server of our platform is the middle-ware responsi- allowed to have to be considered matched. One drawback ble for the communication between the mobile devices and of this measurement is that it ignores distance gaps stores vital data in its database. The server application for- between subsequences, that allows to obtain some points wards the queries of the users to the mobile devices which of the track when alignment. Consequently, it can lead to are registered to our platform. Then it receives the results of inaccuracies in the similarity analysis. each device and the best one, according to the algorithm’s results, is sent back to the user who submitted the Query. 5. Fréchet Distance 4. Trajectory Similarity Measures Given two curves, A, B in a metric space, the Fréchet dis- tance, dF (A, B) is defined as In this section we review the trajectory similarity algo- rithms we use in the system to find the most similar tra- jectories to the query. Dynamic Time Warping: The Dy- dF (A, B) = inf max {d(A((t)), B((t)))} α,β t∈[0,1] namic Time Warping (DTW) (Donald J. Berndt, 1994) is an algorithm for measuring similarity between two tempo- where , range over all monotone reparameterizations and ral sequences which may vary in time or speed. The DTW d(, ) represents the Euclidean distance, and inf is the infi- is widely used in the comparison of time series, appropri- mum. The discrete Fréchet distance dF between two polyg- ately aligns the sequence of points of the two rails, so that onal curves a : [0, m] → Rk and b : [0, n] → Rk is defined the total distance as a sum of individual distances is mini- as: mized. dF (a, b) = DT W(P1..n , Q1..n ) = min max {d(a(σ(s)), b(β(s)))} σ:[1:m+n]→[0:m], s∈[1:m+n] DT W (P1..n−1 , Q1..m−1 ) β:[1:m+n]→[0:n] |Pn − Qn | + min DT W (P1..n−1 , Q1..m ) where σ and β range over all discrete non-decreasing onto DT W (P1..n , Q1..m−1 ) mappings of the form σ : [1 : m + n] → [0 : m], β : [1 : m + n] → [0 : n]. where P1 .. n-1 the subsequence P1 .. n that include ele- We first consider the corresponding decision problem. That ments (points) for time periods of 1 up to n-1. is, given δ > 0, we wish to decide whether δF+ (A, B) ≤ δ. Longest Common SubSequence: The Longest Common Consider the matrix M as defined in the subsection 5.1. SubSequence (LCSS) (Michail Vlachos, 2002)problem is In the two-sided version of Discrete Fréchet Distance with to find the longest subsequence common to all sequences Shortcuts (DFDS), given a reachable position (ai , bj ) of in a set of sequences (often just two). The LCSS algorithm, two pointers, the A-pointer can make a skipping upward using dynamic programming fits best points of the two tra- move, as in the one-sided variant, to any point ak , k > i, jectories based on a tolerance parameter time and a toler- for which Mk,j = 1. Alternatively, the B-pointer can go to ance parameter space ε. It considers that the points do not any point bl , l > j, for which Mi,l = 1; this is a skipping exceed the tolerance parameters fit and attaches similarity right move in M from Mi,j = 1 to Mi,l = 1, defined anal- value equal to 1. If they do not match they are assigned the ogously. Determining whether δF+ (A, B) ≤ δ corresponds value 0. Specifically, the LCSS distance between two real- to deciding whether there exists a sparse staircase of ones valued sequences S1 and S2 of length m and n respectively in M that starts at M1,1 , ends at Mm,n , and consists of is computed as follows: an interweaving sequence of skipping upward moves and skipping right moves (see Figure 2).. Lcss(Pδ,s (S1 , S2 )) = 5.1. Basic Algorithm 0, if n = 0 or m = 0 1 + Lcssδ,s (HEAD(S1 ), HEAD(S2 )) The implementation of the algorithm of Fréchet Distance max(Lcssδ,s (HEAD(S1 ), S2 ), relied on the publication ”The Discrete Fréchet Distance Lcssδ,s (S1 , HEAD(S2 ))) with Shortcuts via Approximate Distance Counting and otherwise Selection” (Anne Driemel),(Rinat Ben Avraham, 2014). Ryy Evaluating distance measures for trajectories in the mobile setting Specifically, the algorithm which was implemented is the of the table (0,0) to the last (N, M) wherein N and M two side - DFDS who faces the problem of outliers which is are the dimensions of the two trajectories which were sensitive the Fréchet Distance. The result of the algorithm compared. If the algorithm of Shortest Path has a so- is the lowest Fréchet distance which satisfies the two tra- lution we check if the value of is between the limits jectories. The pseudocode of the algorithm is represented we have set. In case it is the binary search terminates. in Algorithm 1. The steps of the basic algorithm are the Otherwise, it will perform again with latest prices. If following: not the execution of the algorithm terminates. 1. Implementation of binary search and sequential exe- cutions of the algorithm of Fréchet Distance until the 6. Evaluation optimal distance e is found. The initial value which is given to the middle in the binary search is 0.025. 6.1. Fréchet Distance Performance The binary search is terminated when the distance be- To measure the performance of the algorithm of the Fréchet tween low and high values of the middle is smaller Distance we performed experiments comparing time series than 0.001. with length ranged from 20000 to 100000 points. From 2. Then the table is created, whose columns correspond the paper of Rinat Ben Avraham et all know that the com- the points (latitude, longitude) of trajectory A and the plexity of the algorithm of Fréchet Distance with Shorcuts lines the points of the trajectory B. The values taken (DFDS) is O((m2/3 n2/3 + m + n)log 3 (m + n)). The by the M matrix is either 0 or 1 depending on the dis- main difference with the previous version of the algorithm tance apart of these two points together, and are given is that we calculate table T and simultaneously create also by the following formula: the graph G. In addition we set a parameter δ which rep- resents the percentage of table points that we wish to com- pare. In this way, we improved the time execution of the Eδ+ = algorithm of Fréchet Distance. Also due to the sampling of ((ai , bj ), (ak , bj ))|k > i, ||ai − bj ||, ||ak − bj || ≤ δ δ points in all time series, the complexity of the algorithm ∪((ai , bj ), (ai , bl ))|l > j, ||ai − bj ||, ||ai − bl || ≤ δ is reduced to linear. 3. Forthwith after, the directed graph G is created, based The figure below shows the performance of the implemen- on the table M which was formed above. The nodes tation of the Fréchet Distance algorithm compared with the of the graph are the positions of the table M. Corre- length of the trajectories. In our experiment that is summa- spondingly it is created an edge between two nodes if rized by figure 3 we compared 50 trajectories with lengths the nodes are in the same row or column of the table from 20,000 points to 100,000 points. This experiment was and their values are 1 (from the previous to the next). performed 10 times and for each length of trajectories it was chosen the average execution time. Also, the chart shows the dispersion of runtime for any length of time se- ries on error bars. From figure 3, we can conclude that the complexity of the algorithm is linear. Figure 2. M table Figure 3. Frechet performance 4. In the figure 2, the algorithm Shortest Path is per- formed to see if there is a path from the first position RyR Evaluating distance measures for trajectories in the mobile setting Algorithm 1 Fréchet Distance 6.2. Algorithm Comparison Input: trajectory ti , trajectory query,int delta In this section we show preliminary experimental results Binary Search that compare the three different trajectory similarity meth- repeat ods we have described. The focus of our evaluation is to rightT able[0..trajectory.length][0..1] = null show that all methods can be used in the limited resources downT able[0..trajectory.length][0..1] = null environment of a smartphone. For this reason we also com- for i = 1 to ti .length do pare the run time results with the simpler (easier to imple- start ← i − delta ment and efficient to run) Euclidean distance that serves as if start < 0 then start ← 0 a basic comparison point. It is difficult to compare the three stop ← i + delta methods because they have been implemented with differ- if start > query.length then stop ← query.length ent optimizations, and also our Fréchet distance implemen- for j = start to stop do tation computes only a bound, and necessitates the use of if xi > xi+1 then several runs to compute the exact Fréchet distance. We use M [i][j] ← 1 two different datasets for the comparisons. We also show a if firstExecution then sample result of a query and the most similar answers that if M[0][0] == 0 then we get using the three methods. return else The datasets which were used in the experiments are from graph.addV ertex(0, 0) the chorochronos.org and Dublin Bus GPS sample data end if from Dublin City Council (Insight Project). The param- f irstExecution ← false eters with which we will compare the algorithms perfor- end if mance are their time execution and their results. The name if rightTable[i][0] != ll and rightTable[i][1] != of the dataset from chorochronos.org is Trucks and con- null then tains 50 trajectories. The name of the dataset from In- graph.addV ertex((i, j)) sight project is Siri and contains 30 bus trajectories. For graph.addV ertex((rightT able[i][0], the experiments, the first trajectory of the dataset was used rightT able[i][1])) as a query and compared with the remaining 49 trajecto- graph.addEdge((i, j), ries. The experiments were performed for trajectories with (rightT able[i][0], rightT able[i][1]))) length 2048 points each. rightT able[i][0] ← i At the end of each experiment the program returns the rightT able[i][1] ← j graphs of execution time of each algorithm and the most else similar trajectory chosen by each algorithm. The algo- rightT able[i][0] ← i rithms we compare are: rightT able[i][1] ← j end if if downTable[i][0] != null and downTable[i][1] • Dynamic Time Warping (DTW) != null then graph.addEdge((i, j), (downT able[i][0], • Longest Common Subsequence (LCSS) downT able[i][1]))) downT able[i][0] ← i • Fréchet Distance: DFDS to find the smaller Fréchet downT able[i][1] ← j distance. In order for DFDS to find the smaller else Fréchet distance, the algorithm should be executed downT able[i][0] ← i multiple times for each trajectory that is compared as downT able[i][1] ← j the algorithm described above suggests. (DFDS) end if else M [i][j] ← 0 • Fréchet Distance - one execution of the algorithm end if (DFDS one time) end for end for Bellow we present the results from the data provided by // Find the shortest path if exists on graph from the Insight Project. This dataset containts trajectories recorded // first to the last position of table M from Dublin buses across Dublin City. In comparison with graph.f indShortestP ath() 2048 points per trajectory, the execution time of the algo- until shortestP ath is f alse and f rechetDistance ∈ rithms is presented in figure 4. BinarySearchRange Ryk Evaluating distance measures for trajectories in the mobile setting Figure 4. Algorithms execution time for 2048 points (Dublind Bus GPS sample) Figure 6. LCSS most similar trajectory for 2048 points (Dublind Bus GPS sample) The results of each algorithm that correspond to the most similar trajectory are listed below. In figure 5 is the most similar trajectory according to Dis- crete Fréchet Distance algorithm. Figure 7. DTW most similar trajectory for 2048 points (Dublind Bus GPS sample) Figure 5. DFDS most similar trajectory for 2048 points (Dublind Bus GPS sample) We conducted the same experiments with the dataset pro- In figure 6 is the most similar trajectory according to LCSS vided by chorocronos.org. Specifically with trajectories algorithm. that contain 2048 points. In comparison with 2048 points In figure 7 is the most similar trajectory according to DTW per trajectory the execution time of the algorithms are pre- algorithm. sented in figure 8. Ryj Evaluating distance measures for trajectories in the mobile setting Figure 8. Algorithms execution time for 2048 points (chorochronos.org) Figure 10. LCSS most similar trajectory for 2048 points (chorochronos.org) The results of each algorithm that correspond to the most similar trajectory are listed below. In figure 9 is the most similar trajectory according to Dis- crete Fréchet Distance algorithm Figure 11. DTW most similar trajectory for 2048 points (chorochronos.org) We observe that the distance measurement that have been implemented (Fréchet Distance) have similar execution Figure 9. DFDS most similar trajectory for 2048 points time with the implementation of the LCSS algorithm. (chorochronos.org) However, the final results of the algorithm differ. The ex- ecution time of a single run of Fréchet Distance algorithm is similar to the LCSS’s algorithm execution time. The re- sults of Fréchet Distance algorithm are based on the sim- In figure 10 is the most similar trajectory according to ilarity of the shape of each trajectory in contrast with the LCSS algorithm other algorithm which are restricted to specific points com- In figure 11 is the most similar trajectory according to parison. Furthermore, we avoid the problem of outliers that DTW algorithm Fréchet distance is sensitive to, thereby improving signif- Ry9 Evaluating distance measures for trajectories in the mobile setting icantly the final results. Thus, we see that in comparison Donald J. Berndt, James Clifford. Using dynamic time that we are interested more at having a similar shape rather warping to find patterns in time series. In KDD Work- than smaller distance of each point from the points of the shop, pp. 359–370. AAAI Press, 1994. query trajectory, Fréchet Distance produces better results than the other algorithms. Hence, Fréchet Distance is ideal Giorgos Poulis, Spiros Skiadopoulos, Grigorios Loukides for similarity measurement of the shape of trajectories This Aris Gkoulalas-Divanis. Select-organize-anonymize: A conclusion can be valuable for later implementations and framework for trajectory data anonymization. In Data research. Mining Workshops (ICDMW), 2013 IEEE 13th Interna- tional Conference on, pp. 867 – 874, Dallas, TX, 2013. IEEE. 7. Conclusion Lin, Bin and Su, Jianwen. Shapes based trajectory queries In conclusion, the trajectory similarity search problem have for moving objects. In Proceedings of ACM GIS, pp. a plethora of applications, fact that gives the platform de- 21–30. IEEE, 2005. scribed in this work great potentials. Our system allows the user to send a query that contains a trajectory in or- Michail Vlachos, Dimitrios Gunopulos, George Kollios. der to receive a number of the most similar trajectories that Discovering similar multidimensional trajectories. In have been recorded by other mobile devices that are regis- Data Engineering, 2002. Proceedings. 18th Interna- tered to our system. We described the algorithms that the tional Conference on, pp. 673 – 684, San Jose, CA, 2002. mobile application uses in order to measure the similarity IEEE. between trajectory and finally search for the most similar ones. Moreover, the distributed architecture of our sys- Rinat Ben Avraham, Omrit Filtser, Haim Kaplan Matthew tem grants it great capabilities such as scalability. We have J. Katz Micha Sharir. The discrete frchet distance with evaluated our platform and the implemented algorithms us- shortcuts via approximate distance counting and selec- ing real spatio-temporal data. Our experiments prove the tion. In SOCG’14 Proceedings of the thirtieth annual satisfying performance of our implementation. We com- symposium on Computational geometry, pp. 377, New pared each algorithm that we implemented and we evalu- York, NY, USA, 2014. ACM. ate both their performance and their final results accord- Zeinalipour-Yazti, Demetrios, Laoudias, Christos, Costa, ing to the similarity between the selected trajectory and the Constandinos, Vlachos, Michail, Andreou, Maria I., and query. We extracted useful conclusions about each algo- Gunopulos, Dimitrios. Crowdsourced trace similarity rithm’s functionality and results, such as the different cases with smartphones. In EEE Transactions on Knowledge where the Fréchet distance algorithm is more suitable than and Data Engineering (TKDE ’13), IEEE Computer So- the other distance measures. To sum up the final system ciety, pp. 1240–1253, Los Alamitos, CA, USA, 2013. that was implemented gives a number of final responses to IEEE. queries submitted by its users, according to the selected al- gorithm in a satisfying time. A future goal is to extend the number of distance measurements that are implemented in order for the system to have more reliable and accurate final results. 8. Acknowledgements We would like to thank Demetris Zeinalipour-Yazti, ”Uni- versity of Cyprus” for his assistance by providing us the source code of the implementation of LCSS algorithm. This research was supported by the ARISTEIA MMD, FP7 INSIGHT, ERC IDEAS NGHCS and THALIS GeomComp projects. References Anne Driemel, Sariel Har-Peled, Carola Wenk. Approxi- mating the Frchet Distance for Realistic Curves in Near Linear Time. Ry8