ALGORITMA PENCARIAN TETANGGA TERDEKAT MENGGUNAKAN POHON K-DIMENSI BERBASIS MAPREDUCE UNTUK MEMPREDIKSI TUJUAN AKHIR PERJALANAN TAKSI; NEAREST NEIGHBOR SEARCH ALGORITHM USING K-DIMENSIONAL TREE BASED ON MAPREDUCE TO PREDICT THE DESTINATION OF TAXI TRIPS

ZAINURROHMAN, BASITH, Nur Rokhman

2016 | Skripsi | FMIPA

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 : Nearest neighbor searching, k-dimensional tree, MapReduce, Hadoop