面向凝聚式层次聚类算法实现的矩阵存储数据结构研究

An Approach on the Data Structure for the Matrix Storing Based on the Implementation of Agglomerative Hierarchical Clustering Algorithm

快速查找、扩张、收缩是凝聚式层次聚类算法快速实现对相似度/距离矩阵存储的基本要求。本文提出了基于十字链表和平衡二叉树的复合数据结构 CrossAVL 用于矩阵的存储,给出了查找、扩张,收缩操作的实现并对其时间复杂度进行了分析。实验结果表明,CrossAVL 对快速要求能够较好地满足。

Searching, expanding, shrinking instantly is the precondition of the similarity/distance matrix storing for the implementation of agglomerative hierarchical clustering algorithm. This paper presents a new compound data structure named as CrossAVL based on cross list and AVL tree for the matrix storing. The time complexity for the implementa tion of searching, expanding and shrinking method based on CrossAVL are given. Experimental results show that all those method can be running instantly.