Fast reciprocal nearest neighbors clustering

This paper presents a novel approach for accelerating the popular reciprocal nearest neighbors (RNN) clustering algorithm, i.e. the fast-RNN. We speed up the nearest neighbor chains construction via a novel dynamic slicing strategy for the projection search paradigm. We detail an efficient implementation of the clustering algorithm along with a novel data structure, and present extensive experimental results that illustrate the excellent performance of fast-RNN in low- and high-dimensional spaces. A C++ implementation has been made publicly available.

► We present a fast version of the reciprocal nearest neighbors (RNN) clustering. ► The approach is based on an efficient dynamic space partitioning strategy. ► A novel data structure improves the performance with low- and high-dimensional data. ► Results show that the fast-RNN is faster than the standard RNN. ► A C++ implementation of the algorithm has been made publicly available.