Fast agglomerative clustering using a k-nearest neighbor graph

We propose a fast agglomerative clustering method using an approximate nearest neighbor graph for reducing the number of distance calculations. The time complexity of the algorithm is improved from Od(tau N-2) to Od (tau N logN) at the cost of a slight increase in distortion; here, tau denotes the number of nearest neighbor updates required at each iteration. According to the experiments, a relatively small neighborhood size is sufficient to maintain the quality close to that of the full search.