Robust and efficient cluster analysis using a shared near neighbours approach

A nonparametric method for clustering multidimensional data in O(nlogn) time is described. It is based on the shared near neighbours algorithm. It uses adaptive k-d trees combined with various other sophisticated data structures to significantly decrease the computational complexity of the original algorithm which was O(n² ). The algorithm is suitable for a wide range of data and capable of delineating clusters of varying shape, density, and homogeneity. A comprehensive set of results is presented