Grid-Clustering: A Fast Hierarchical Clustering Method for very Large Data Sets
Erich Schikut
Abstract
This paper presents a new approach to hierarchical clustering of very large data sets, named Grid-Clustering. The method organizes unlike the conventional methods the space surrounding the patterns and not the patterns. It uses a multidimensional grid data structure. The resulting block partitioning of the value space is clustered via a topological neighbor search. The Grid-Clustering method is able to deliver structural pattern distribution information for very large data sets. It superceeds all conventional hierarchical algorithms in runtime behavior and memory space requirements. The algorithm was analyzed within a testbed and suitable values for the tunable parameters of the algorithm are proposed.  A comparison of the executions times to other commonly used clustering algorithms and a heuristic runtime analysis is given.