Figure 4: K-tree Construction in the collection is assigned a random vector, and the document term occurrence vector is then a superposi- tion of all the term random vectors. There is no matrix decomposition and hence the process is efficient. The RI process is conceptually very different from LSA and does not have the same optimality properties. The context vectors used by RI should optimally be orthogonal. Nearly orthogonal vectors can be used and have been found to perform similarly [4]. These vec- tors can be drawn from a random Gaussian distribution. The Johnson and Linden-Strauss lemma [11] states that if points are projected into a randomly selected sub- space of sufficiently high dimensionality, then the dis- tances between the points are approximately preserved. The same topology that exists in the higher dimensional space is reflected in the lower dimensional randomly se- lected subspace. Consequently, RI offers low complex- ity dimensionality reduction while still preserving the topological relationships amongst document vectors. term matrix D and a term by index-vector matrix I . Al- ternatively, I can be referred to as a random projection matrix. Each row vector in D represents a document, each row vector in I is an index vector, n is the number of documents, t is the number of terms and r is the dimensionality of the reduced spaced. R is the reduced matrix where each row vector represents a document. In RI, each dimension in the original space is given a randomly generated index vector. The index vectors are high dimensional, sparse and ternary. Sparsity is controlled via a seed length that specifies the number of randomly selected non-zero dimensions. Ternary vec- tors consist of randomly distributed +1 and -1 values in the non-zero dimensions. In the context of document clustering, RI can be viewed as a matrix multiplication of a document by The index vectors used in RI were chosen to be sparse and ternary. Ternary index vectors for RI were introduced by Achlioptas [2] as being well suited for database environments. The primary concern of sparse index vectors is reducing time and space complexity. Bingham and Mannila [4] run experiments indicating RI has several advantages. It can be performed in- crementally and on-line as data arrives. Any document can be indexed (i.e. encoded as an RI vector) inde- pendently from all other documents in the collection. This eliminates the need to build and store the entire document by term matrix. Additionally, newly encoun- tered dimensions (terms) in the document collection are easily accommodated without having to recalculate the projection of previously encoded documents. In con- trast, SVD requires global analysis where the number of documents and terms are fixed. The time complexity of RI is also very attractive. It is linear in the number of terms in a document and independent of collection size. 3.2 Choice of Index Vectors 3.1 Random Indexing Definition D n$_{×}$t I t$_{×}$r = R n$_{×}$r (4) node vector child link k-means performed on enclosed vectors the dashed parts represent the nearest neighbour search level 1 level 2 level 3 root node nodes above the leaves contain codebook vectors leaf nodes contain the data vectors nodes above the codebook level are clusters of clusters