Algoritma pencarian tetangga terdekat telah dikenal luas untuk mencari kemiripan suatu objek terhadap objek lainnya sehingga implementasinya biasa digunakan pada bidang pengenalan pola, penggalian data, pengolahan citra, dan lain-lain. Algoritma ini dioptimasi dalam stuktur data pohon k-dimensi. Hal ini dilakukan dengan melewatkan objek pencarian yang tidak mungkin menghasilkan hasil yang optimal sehingga mempercepat waktu proses pencarian. Implementasi suatu algoritma yang berjalan secara paralel dan terdistribusi telah menjadi objek penelitian yang sangat diminati pada dekade terakhir ini. Hal ini dilakukan untuk menangani data berskala besar. Salah satu model implementasi yang digunakan dalam penanganan data besar adalah MapReduce. Akan tetapi, library yang dapat dimanfaatkan untuk keperluan penggalian data menggunakan model ini belum banyak tersedia. Salah satunya adalah algoritma pencarian tetangga terdekat menggunakan pohon k-dimensi. Dalam penelitian ini dikembangkan algoritma pencarian tetangga terdekat menggunakan pohon k-dimensi yang berjalan secara paralel dan terdistribusi menggunakan model MapReduce. Program ini dijalankan di atas kerangka kerja Apache Hadoop. Penelitian ini dilakukan dengan menguji 1.7 juta data titik query terhadap 2888, 4138, dan 5439 pusat klaster objek data spasial berupa koordinat GPS trayek taksi sebagai data pelatihan. Hal ini dijalankan pada 1 hingga 5 mesin. Hasilnya algoritma ini mampu berjalan sekitar 400000 ms pada 5 mesin.

The nearest neighbor search algorithm has been widely used to search similarity of object toward the other object, so that the implementation commonly used for subject such as pattern recognition, data mining, image processing, and so on. This algorithm can be optimized by using k-dimensional tree. This is done by skipping searching object which does not produce optimal result so this mechanism can accelerate the running time of searching process. The implementation of algorithm which running in parallel and distributed has become an interest research object in recent decades. It is used to handle large scale data. One implementation model that used for handling big data is MapReduce. However, there are few libraries available that could be used for data mining cases with MapReduce technique. One of which is the nearest neighbor search algorithm using k-dimensional tree. In this research, nearest neighbor with k-dimensional tree which running in parallel and distributed technique based on MapReduce has been developed. The program is running on Apache Hadoop framework. This research is done by testing about 1.7 million of query data toward 2888, 4138, and 5439 centroids of cluster data which is spatial data object, GPS coordinate of taxi trajectory as training data. It runs on 1 until 5 machines. The result, this algorithm can run about 400000 ms on 5 machines.

Kata Kunci : pencarian tetangga terdekat, pohon k-dimensi, MapReduce, Hadoop