Analisis Perbandingan Performa Algoritme Voronoi-Based Continuous K Nearest Neighbor Dan Dijkstra Dalam Mengelola Data Berukuran Besar (Studi Kasus : Malang Raya)

Abstrak

Salah satu kriteria dalam penerapan mobile navigation adalah kemampuan perangkat mobile untuk terus memantau titik atau objek akses dari pengguna, namun dalam melakukan pemantauan titik atau objek selalu terjadi perubahan yang dikarenakan pergerakan dari pengguna. Perubahan yang terjadi dikenal sebagai split nodes. Terdapat metode yang digunakan untuk mengelola split nodes yaitu KNN search, namun performa yang dihasilkan masih belum memuaskan. Metode lain yang diusulkan adalah algoritme Voronoi Continuous K Nearest Neighbor (VCKNN) yang menggunakan diagram Voronoi untuk membantu mengelola split nodes. Penggunaan algoritme VCKNN didukung oleh algoritme Dijkstra dalam melakukan pencarian split nodes di dalam poligon Voronoi. Pada penelitian ini akan dilakukan perbandingan antara algoritme VCKNN dan Dijkstra dalam mengelola split nodes. Hal ini dilakukan untuk mendapatkan algoritme yang memiliki performa terbaik dalam mengelola data pada aspek pembagian segmentasi, runtime dan jumlah split nodes. Penelitian ini akan mengambil studi area Malang Raya. Pemilihan Malang Raya sebagai studi area dikarenakan struktur jaringan jalan yang belum tertata rapih, sehingga dapat diketahui performa dari algoritme yang diusulkan. Dari penelitian ini didapatkan hasil menggunakan algoritme VCKNN terjadi peningkatan performa yang dihasilkan dibandingkan dengan algoritme Dijkstra. Peningkatan performa yang terjadi dikarenakan penurunan jumlah split nodes yang dihasilkan. Penurunan split nodes yang terjadi menggunakan algoritme VCKNN berdasarkan penggunaan batas administrasi Kelurahan sebagai interest point menghasilkan penurunan split nodes sebesar 92,4%. Dengan hasil penelitian ini untuk kondisi jaringan jalan Malang Raya, algoritme VCKNN menghasilkan hasil yang memuaskan.