Similarity Analysis of User Trajectories Based on Haversine Distance and Needleman Wunsch Algorithm
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
Full Text:
PDFReferences
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
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
P-ISSN : 2460-8912
E-ISSN : 2460-8920
ELKAWNIE
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Elkawnie: Journal of Islamic Science and Technology in 2022. 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