Name
Title | ||
|---|---|---|
NNB: An efficient nearest neighbor search method for hierarchical clustering on large datasets |
Abstract | ||
|---|---|---|
Nearest neighbor search is a key technique used in hierarchical clustering. The time complexity of standard agglomerative hierarchical clustering is O(n3), while the time complexity of more advanced hierarchical clustering algorithms (such as nearest neighbor chain) is O(n2). This paper presents a new nearest neighbor search method called nearest neighbor boundary(NNB), which first divides a large dataset into independent subsets and then finds nearest neighbor of each point in the subsets. When NNB is used, the time complexity of hierarchical clustering can be reduced to O(n log2n). Based on NNB, we propose a fast hierarchical clustering algorithm called nearest-neighbor boundary clustering(NBC), and the proposed algorithm can also be adapted to the parallel and distributed computing frameworks. The experimental results demonstrate that our proposal algorithm is practical for large datasets. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/ICOSC.2015.7050840 | IEEE International Conference on Semantic Computing |
Keywords | Field | DocType |
Hierarchical clustering, nearest neighbor boundary, parallel and distributed computing, MapReduce | Hierarchical clustering,Canopy clustering algorithm,Data mining,CURE data clustering algorithm,Pattern recognition,Computer science,Best bin first,Nearest neighbor graph,Nearest-neighbor chain algorithm,Artificial intelligence,Nearest neighbor search,Single-linkage clustering | Conference |
ISSN | Citations | PageRank |
2325-6516 | 1 | 0.36 |
References | Authors | |
15 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wei Zhang | 1 | 1221 | 180.16 |
| Gongxuan Zhang | 2 | 94 | 19.89 |
| Yong-li Wang | 3 | 107 | 26.46 |
| Zhaomeng Zhu | 4 | 5 | 2.48 |
| Tao Li | 5 | 1 | 0.36 |