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

• similarity of trajectories
• linear interpolation
• haversine distance
• global alignment