Mobile Computing, Applications, and Services. 10th EAI International Conference, MobiCASE 2019, Hangzhou, China, June 14–15, 2019, Proceedings

Research Article

Comparison of User Trajectories with the Needleman-Wunsch Algorithm

Download
7 downloads
  • @INPROCEEDINGS{10.1007/978-3-030-28468-8_11,
        author={Maroš Čavojsk\"{y} and Martin Drozda},
        title={Comparison of User Trajectories with the Needleman-Wunsch Algorithm},
        proceedings={Mobile Computing, Applications, and Services. 10th EAI International Conference, MobiCASE 2019, Hangzhou, China, June 14--15, 2019, Proceedings},
        proceedings_a={MOBICASE},
        year={2019},
        month={9},
        keywords={GPS Needleman-Wunsch algorithm Sequence alignment User movement patterns Experimental evaluation},
        doi={10.1007/978-3-030-28468-8_11}
    }
    
  • Maroš Čavojský
    Martin Drozda
    Year: 2019
    Comparison of User Trajectories with the Needleman-Wunsch Algorithm
    MOBICASE
    Springer
    DOI: 10.1007/978-3-030-28468-8_11
Maroš Čavojský1,*, Martin Drozda1,*
  • 1: Slovak University of Technology
*Contact email: maros.cavojsky@stuba.sk, martin.drozda@stuba.sk

Abstract

We show that the Needleman-Wunsch algorithm for sequence alignment can be efficiently applied to comparing user trajectories, where user locations are provided by Global positioning system (GPS). We compare our approach based on this algorithm with other approaches such as the pairwise method and the proximity method. We describe all steps necessary to apply the Needleman-Wunsch algorithm when comparing user trajectories. In our experiments we use two different data sets: a data set that we collected with 455 mobile devices distributed among our students and the Geolife data set (Microsoft Research Asia). We conclude that our approach based on the Needleman-Wunsch algorithm performs better than other approaches, especially, in terms of true negatives, false positives and false negatives, while still offering improvement in terms of true positives.