Abstract Random Indexing (RI) K-tree is the combi- nation of two algorithms for clustering. Many large scale problems exist in document clustering. RI K-tree scales well with large inputs due to its low complexity. It also exhibits features that are useful for managing a changing collection. Furthermore, it solves previ- ous issues with sparse document vectors when using K- tree. The algorithms and data structures are defined, explained and motivated. Specific modifications to K- tree are made for use with RI. Experiments have been executed to measure quality. The results indicate that RI K-tree improves document cluster quality over the original K-tree algorithm. 

Keywords Random Indexing, K-tree, Dimensionality Reduction, B-tree, Search Tree, Clustering, Document Clustering, Vector Quantization, k-means 

## 1 Introduction 

The purpose of this paper is to present and analyse the combination of Random Indexing (RI) with the K-tree algorithm. Both RI and K-tree adapt to changing data and decrease the cost of computationally intensive vector based applications. This combination is particularly suitable to the representation and clustering of very large document collections. Documents are typically represented in vector space as very sparse high dimensional vectors. RI can reduce the dimensionality and sparsity of this representation. In turn, the condensed representation is highly effective when working with K-tree. The paper is focused on determining the effectiveness of using RI with K-tree through experiments and comparative analysis of results. 

Sections 2 to 6 discuss K-tree, Random Indexing, Document Representation, Experimental Setup and Ex- perimental results respectively. The paper ends with a conclusion in Section 7. 

## 2 K-tree 

K-tree [6, 1] is a height balanced cluster tree. It was first introduced in the context of signal processing by Geva 

Proceedings of the 14th Australasian Document Comput- ing Symposium, Sydney, Australia, 4 December 2009. Copyright for this article remains with the authors. 

Christopher M. De Vries Lance De Vine Shlomo Geva 

chris@de-vries.id.au l.devine@qut.edu.au s.geva@qut.edu.au 

# Random Indexing K-tree 

Faculty of Science and Technology Queensland University of Technology Brisbane, Australia 

[10]. The algorithm is particularly suitable to clustering of large collections due to its low complexity. It is a hybrid of the B $^{+}$-tree and k-means algorithm. The B $^{+}$-tree algorithm is modified to work with multi di- mensional vectors and k-means is used to perform node splits in the tree. K-tree is also related to Tree Struc- tured Vector Quantization (TSVQ) [9]. TSVQ recur- sively splits the data set, in a top-down fashion, using k-means. TSVQ does not generally produce balanced trees. 

K-tree achieves its efficiency through execution of the high cost k-means step over very small subsets of the data. The number of vectors clustered during any step in the K-tree algorithm is determined by the tree order (usually ≪ 1000) and it is independent of collec- tion size. It is efficient in updating the collection while maintaining clustering properties through the use of a nearest neighbour search tree that directs new vectors to the appropriate leaf node. 

The K-tree forms a hierarchy of clusters. This hi- erarchy supports multi-granular clustering where gen- eralisation or specialisation is observed as the tree is traversed from a leaf towards the root or vice versa. The granularity of clusters can be decided at run-time by selecting clusters that meet criteria such as distortion or cluster size. 

## 2.1 K-tree and Document Clustering 

The K-tree algorithm is well suited to clustering large document collections due to its low time complexity. The time complexity of building K-tree is O(n log n) where n is the number of bytes of data to cluster. This is due to the divide and conquer properties inherent to the search tree. De Vries and Geva [5, 6] investigate the run-time performance and quality of K-tree by compar- ing results with other INEX submissions and CLUTO [13]. CLUTO is a popular clustering tool kit used in the information retrieval community. K-tree has been com- pared to k-means, including the CLUTO implementa- tion, and provides comparable quality and a marked in- crease in run-time performance. However, K-tree forms a hierarchy of clusters and k-means does not. Com- parison of the quality of the tree structure will be un- dertaken in further research. The run-time performance increase of K-tree is most noted when a large number of clusters are required. This is useful in terms of doc- 

