A clustering algorithm for huge trees

We present a new tree clustering algorithm based on combinatorial statistics on trees. Using well-known measures on trees giving the number of leaves of a subtree or the number of siblings of a node, we design a parameter that can be used to detect irregularities in a tree. We obtain a clustering approach for trees by implementing classical statistical tests on this parameter, thus providing well balanced drawings of trees offering better aspect ratios which can be useful when dealing with large, irregular hierarchical data. Our algorithm is linear in time and can thus be applied to large data structures. Moreover the larger the structure is the better the precision of the statistical tools. (C) 2003 Elsevier Inc. All rights reserved.