Research Article
Comparison of User Trajectories with the Needleman-Wunsch Algorithm
@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
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.