Which Fast Nearest Neighbour Search Algorithm to Use?

Abstract. Choosing which fast Nearest Neighbour search algorithm to use depends on the task we face. Usually kd-tree search algorithm is selected when the similarity function is the Euclidean or the Manhattan distances. Generic fast search algorithms (algorithms that works with any distance function) are only used when there is not specific fast search algorithms for the involved distance function. In this work we show that in real data problems generic search algo-rithms (i.e. MDF-tree) can be faster that specific ones (i.e. kd-tree).