ument clustering because there are a huge number of topics in a typical collection. The on-line and incre- mental nature of the algorithm is useful for managing changing document collections. Most clustering algo- rithms are one shot and must be re-run when new data arrives. K-tree adapts as new data arrives and has the low time complexity of O(log n) for insertion of a single document. Additionally, the tree structure also allows for efficient disk based implementations when the size of data sets exceeds that of main memory. K-tree builds a nearest neighbour search tree over a set of real valued vectors V in d dimensional space. It is inspired by the B $^{+}$-tree where all data records are stored in leaf nodes. Tree nodes, N , consist of a se- quence of (vector, child node) pairs of length l . The tree order, m , restricts the number of vectors stored in any node to between one and m . The tree consists of two types of nodes. Leaf nodes contain the data vectors that were inserted into the tree. Internal nodes contain clusters. A cluster vector is the mean of all data vectors contained in the leaves of all descendant nodes (i.e. the entire cluster sub-tree). This follows the same recursive definition of a B $^{+}$-tree where each tree is made up of a set of smaller sub-trees. Upon construction of the tree, a nearest neighbour search tree is built in a bottom-up manner by splitting full nodes using k-means [14] where k = 2 . As the tree depth increases it forms a hierarchy of “clusters of clusters” from the root to the above-leaf level. The above-leaf level contains the finest granularity cluster vectors. Each leaf node stores the data vectors pointed to by the above-leaf level. The efficiency of K-tree stems from the low complexity of the B $^{+}$-tree algorithm, combined with only ever executing k-means on a relatively small number of vectors, defined by the tree order, and by using a small value of k . All the document vectors created by RI are of unit length in the modified K-tree. Therefore, all centroids are normalised to unit length at all times. The k-means used for node splits in K-tree was changed to use ran- domised seeding and restart if it did not converge within six iterations. The process always converged quickly in our experiments; although it is possible to constrain the number of restarts we did not find this to be necessary. The K-tree algorithm was modified for use with RI. This modified version will be referred to as “Modified K-tree” and the original K-tree will be referred to as “Unmodified K-tree”. The K-tree is constructed dynamically as data vectors arrive. Initially the tree contains a single empty root node at the leaf level. Vectors are inserted via a nearest neighbour search, terminating at the leaf level. The root of an empty tree is a leaf, so the first m data vectors are stored in the root, at which point the node becomes full. When the m + 1 vector arrives the root is split using k-means where k = 2 , clustering all m + 1 vectors into two clusters. The two centroids that result from k-means are then promoted to become the centroids in a new root. The vectors associated with each centroid Figures 1 to 3 are K-tree clusters in two dimensions. 1000 points were drawn from a random normal distri- bution with a mean of 1.0 and standard deviation of 0.3. The order of the K-tree, m , was 11. The grey dots repre- sent the data set, the black dots represent the centroids and the lines represent the Voronoi tessellation of the centroids. Each of the data points contained within each tile of the tessellation are the nearest neighbours of the centroid and belong to the same cluster. It can be seen that the probability distribution is modelled at different granularities. The top level of the tree is level 1. It is the coarsest grained clustering. In this example it splits the distribution in three. Level 2 is more granular and splits the collection into 19 sub-clusters. The individual clusters in level 2 can only be arrived at through a near- est neighbour association with a parent cluster in level 1 of the tree. Level 3 is the deepest level in the tree consisting of cluster centroids. The 4th level is the data set of vectors that were inserted into the tree. The original K-tree algorithm does not modify any of the centroids. They are simply the means of the vectors they represent. The k-means implementation runs to complete convergence and seeds centroids via perturbation of the global mean. To create two seeds the global mean is calculated and then the two seeds are created by moving away from the mean in opposite directions. 2.2 K-tree Definition 2.4 K-tree Example Figure 1: Level 1 1 ≤ l ≤ m (2) N = 〈 ( v$_{1}$, c$_{1}$ ) , ..., ( v l , c l ) 〉 (3) ∀ v ∈ V : v ∈ R d (1) 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2.5 Building K-tree 2.3 Modifications to K-tree