Fast PNN-based Clustering Using K-nearest Neighbor Graph

Pasi Fränti, Olli Virmajoki, Ville Hautamäki

Abstract

Search for nearest neighbor is the main source of computation in most clustering algorithms. We propose the use of nearest neighbor graph for reducing the number of candidates. The number of distance calculations per search can be reduced from O(N) to O(k) or where N is the number of clusters, and k is the number of neighbors in the graph. We apply the proposed scheme within agglomerative clustering algorithm known as the PNN algorithm.
BibTeX
@inproceedings{franti2003fast,
  author = {Pasi Fränti and Olli Virmajoki and Ville Hautamäki},
  title = {{Fast PNN-based Clustering Using K-nearest Neighbor Graph}},
  booktitle = {ICDM},
  year = {2003},
  url = {https://openreview.net/forum?id=t70yxRSs0xk},
}

Loading related content...

Figure