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

Authors

  • Mohammad Jamhuri Department of Mathematics, Faculty of Science and Data Analytics, Institut Teknologi Sepuluh Nopember, Surabaya Department of Mathematics, Faculty of Science and Technology, UIN Maulana Malik Ibrahim, Malang
  • Mohammad Isa Irawan Department of Mathematics, Faculty of Science and Data Analytics, Institut Teknologi Sepuluh Nopember, Surabaya
  • Imam Mukhlash Department of Mathematics, Faculty of Science and Technology, UIN Maulana Malik Ibrahim, Malang

DOI:

https://doi.org/10.22373/ekw.v7i2.9232

Keywords:

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

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%.

Author Biographies

  • Mohammad Jamhuri, Department of Mathematics, Faculty of Science and Data Analytics, Institut Teknologi Sepuluh Nopember, Surabaya Department of Mathematics, Faculty of Science and Technology, UIN Maulana Malik Ibrahim, Malang
    Matematika
  • Mohammad Isa Irawan, Department of Mathematics, Faculty of Science and Data Analytics, Institut Teknologi Sepuluh Nopember, Surabaya
    Matematika
  • Imam Mukhlash, Department of Mathematics, Faculty of Science and Technology, UIN Maulana Malik Ibrahim, Malang
    Matematika

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.

Downloads

Additional Files

Published

2022-01-17

Issue

Vol. 7 No. 2 (2021)

Section

Articles

License

Proposed Policy for Journals That Offer Open Access Authors who publish with the Elkawnie journal agree to the following terms:

a. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

b. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

c. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (see The Effect of Open Access).