Similarity Analysis of User Trajectories Based on Haversine Distance and Needleman Wunsch Algorithm

Mohammad Jamhuri, Mohammad Isa Irawan, Imam Mukhlash

Abstract


Abstract: In this paper, we discuss the similarity between two trajectories using the Needleman Wunsch algorithm. The calculation steps are interpolating the trajectory, calculating the distance between the trajectory coordinates, identifying the equivalent length, transforming trajectories into a sequence of alphabetic letters, aligning the sequences, and measuring the magnitude of the similarity based on the alignment results. The similarity obtained is compared directly to the length of the trajectories shared by the two lines. The calculation results show that the accuracy of the alignment method reaches more than 90%. 

Abstrak: Dalam tulisan ini dibahas cara perhitungan persentase kesamaan dari dua buah lintasan menggunakan algoritma Needleman Wunsch dan perhitungan secara manual berdasarkan irisan dari lintasan-lintasan tersebut. Pada perhitungan menggunakan algoritma Needleman Wunsch, tahapan-tahapan yang dilakukan adalah menginterpolasi lintasan, menghitung jarak antara titik-titik koordinat dari kedua lintasan, mengidentifikasi jarak yang ekivalen, mengubah lintasan menjadi sekuens huruf alfabet, menyejajarkan sekuens, dan menentukan besarnya kesamaan berdasarkan hasil penyejajaran. Kesamaan yang diperoleh dari metode penyejajaran dibandingkan secara langsung dengan panjang jalur yang dilalui bersama oleh kedua lintasan, hasil perhitungan menunjukkan bahwa akurasi metode penyejajaran mencapai lebih dari 90%.

Keywords


similarity of trajectories; linear interpolation; Haversine distance; global alignment

Full Text:

PDF

References


Anisya, A., & Swara, G. Y. (2017). Implementation of Haversine Formula and Best First Search Method in Searching of Tsunami Evacuation Route. IOP Conference Series: Earth and Environmental Science, 97(1). https://doi.org/10.1088/1755-1315/97/1/012004

Beretta, S. (2018). Algorithms for strings and sequences: Pairwise alignment. In Encyclopedia of Bioinformatics and Computational Biology: ABC of Bioinformatics (Vols. 1–3). Elsevier Ltd. https://doi.org/10.1016/B978-0-12-809633-8.20317-8

Boubrahimi, S. F., Aydin, B., Schuh, M. A., Kempton, D., Angryk, R. A., & Ma, R. (2018). Spatiotemporal interpolation methods for solar event trajectories. The Astrophysical Journal Supplement Series, 236(1), 23.

Čavojský, M., & Drozda, M. (2019). Comparison of user trajectories with the Needleman-Wunsch algorithm. International Conference on Mobile Computing, Applications, and Services, 141–154.

Čavojský, M., Drozda, M., & Balogh, Z. (2020). Analysis and experimental evaluation of the Needleman-Wunsch algorithm for trajectory comparison. Expert Systems with Applications, 165(May 2020). https://doi.org/10.1016/j.eswa.2020.114068

Chapra, S. C., & Canale, R. P. (1998). Numerical methods for engineers.

Chen, L., Özsu, M. T., & Oria, V. (2005). Robust and fast similarity search for moving object trajectories. Proceedings of the ACM SIGMOD International Conference on Management of Data, 491–502. https://doi.org/10.1145/1066157.1066213

Chua, S. L., & Foo, L. K. (2015). Sensor Selection in Smart Homes. Procedia Computer Science, 69, 116–124. https://doi.org/10.1016/j.procs.2015.10.012

Garhwal, A. S., & Yan, W. Q. (2019). BIIIA: a bioinformatics-inspired image identification approach. Multimedia Tools and Applications, 78(8), 9537–9552. https://doi.org/10.1007/s11042-018-6551-y

Inman, J. (1849). Navigation and Nautical Astronomy, for the Use of British Seamen. F. & J. Rivington.

Irawan, M. I., Mukhlash, I., Rizky, A., & Dewi, A. R. (2019). Application of Needleman-Wunch Algorithm to identify mutation in DNA sequences of Corona virus. Journal of Physics: Conference Series, 1218(1), 12031.

Ju, S., Park, S., Lim, H., Yun, S. B., & Heo, J. (2018). Spatial-data-driven student characterization: Trajectory sequence alignment based on student smart card transactions. Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Prediction of Human Mobility, PredictGIS 2018, 1–7. https://doi.org/10.1145/3283590.3283591

Magdy, N., Abdelkader, T., & El-Bahnasy, K. (2018). A comparative study of similarity evaluation methods among trajectories of moving objects. Egyptian Informatics Journal, 19(3), 165–177. https://doi.org/10.1016/j.eij.2018.03.001

Mello, R. dos S., Bogorny, V., Alvares, L. O., Santana, L. H. Z., Ferrero, C. A., Frozza, A. A., Schreiner, G. A., & Renso, C. (2019). MASTER: A multiple aspect view on trajectories. Transactions in GIS, 23(4), 805–822.

Needleman, S. B., & Wunsch, C. D. (1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443–453. https://doi.org/10.1016/0022-2836(70)90057-4

Sabarish, B. A., Karthi, R., & Kumar, T. G. (2020). Graph Similarity-based Hierarchical Clustering of Trajectory Data. Procedia Computer Science, 171(2019), 32–41. https://doi.org/10.1016/j.procs.2020.04.004

Sofwan, A., Soetrisno, Y. A. A., Ramadhani, N. P., Rahmayani, A., Handoyo, E., & Arfan, M. (2019). Vehicle Distance Measurement Tuning using Haversine and Micro-Segmentation. 2019 International Seminar on Intelligent Technology and Its Applications (ISITIA), 239–243.

Toohey, K., & Duckham, M. (2015). Trajectory similarity measures. SIGSPATIAL Special, 7(1), 43–50. https://doi.org/10.1145/2782759.2782767

Wang, H., Su, H., Zheng, K., Sadiq, S., & Zhou, X. (2013). An effectiveness study on trajectory similarity measures. Conferences in Research and Practice in Information Technology Series, 137(February), 13–22.




DOI: http://dx.doi.org/10.22373/ekw.v7i2.9232

Refbacks

  • There are currently no refbacks.


Copyright (c) 2021 Mohammad Jamhuri, Mohammad Isa Irawan, Imam Mukhlash

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

P-ISSN : 2460-8912
E-ISSN : 2460-8920

ELKAWNIE

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Elkawnie: Journal of Islamic Science and Technology in 2020. Published by Faculty of Science and Technology in cooperation with Center for Research and Community Service (LP2M), UIN Ar-Raniry Banda Aceh, Aceh, Indonesia.

View full page view stats report click here

Flag Counter