=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== https://ceur-ws.org/Vol-1392/paper-16.pdf
           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 is where:

                                                                     • 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