Probabilistic analysis of the RNN-CLINK clustering algorithm
Sheau-Dong Lang, Li-Jen Mao, Wen-Lin Hsu · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1999
Clustering is among the oldest techniques used in data mining applications. Typical implementations of the hierarchical agglomerative clustering methods (HACM) require an amount of O(N2)-space, when there are N data objects, making such algorithms impractical for problems involving large datasets. The well-known clustering algorithm RNN- CLINK requires only O(N)-space, but O(N3)-time in the worst case, although the average time appears to be O(N2-log N). We provide a probabilistic interpretation of the average time complexity of the algorithm. We also report experimental results, using the randomly generated bit vectors, and using the NETNEWS articles as the input, to support our theoretical analysis.