Format

Send to

Choose Destination
IEEE Trans Pattern Anal Mach Intell. 2006 Nov;28(11):1875-81.

Fast agglomerative clustering using a k-nearest neighbor graph.

Author information

1
Speech and Image Processing Unit, Department of Computer Science, University of Joensuu, Finland. franti@cs.joensuu.fi

Abstract

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 O(tauN2) to O(tauNlogN) 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.

PMID:
17063692
DOI:
10.1109/TPAMI.2006.227
[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for IEEE Engineering in Medicine and Biology Society
Loading ...
Support Center