Evaluating Algorithms for Nearest Neighbor Searches in Spatial Databases Using R-Trees

Abstract

This Master thesis is on the discussion and research of the topic Nearest Neighbors in Spatial Databases using R-trees. Carried out at The Norwegian University of Science and Technology as part of the study program Master of Science, Informatics: Databases and Search during the autumn 2016 and spring 2017. In cooperation with Oracle Norge, MySQL department. The feature of nearest neighbor searches has been a long awaited functionality in MySQL and is why this project was proposed. This thesis looks at several different data structures and algorithms for solving the nearest neighbor problem. The incremental nearest neighbor algorithm implemented for this thesis showed very good results in terms of speed and functionality.