Figure 5: Random Indexing Example that sparse index vectors do not affect the quality of results. This is not the only choice when creating index vectors. Kanerva [12] introduces binary spatter codes. Plate [15] explores Holographic Reduced Representations that consist of dense vectors with floating point values. In practice, to construct a document vector, the docu- ment vector is initially set to zero, and then the sparse index vector for each term in the document is added to the document vector. The weight of the added term index vector may be determined by TF-IDF or another weighting scheme. When all terms have been added, the document vector is normalised to unit length. There is no need to explicitly form the random projection ma- trix in Equation 4 up-front. The random index vectors for each term can be generated and stored as they are first encountered. The fact that each index vector is sparse means that the vectors use less memory to store and are faster to add. The effect of this approach is that each document will have a particular signature that can be compared with other documents via cosine similarity. The docu- ment signature is thus a vector on the unit hyper-sphere. In the simple scenario in Figure 5 the index vectors for the four words travel, mars, space and telescope, are added to the document vector as they are encountered in the text of the document. Afterwards, the document should be normalised. The sparse index vectors can be efficiently stored by simply storing the position of the non-zero entries with the sign of the position indicating whether it is one or negative one. The time complexity of K-tree depends on the length of the document vectors. K-tree insertion incurs two costs, finding the appropriate leaf node for insertion and k-means invocation during node splits. It is therefore desirable to operate with lower dimensional vector rep- resentation. The combination of RI with K-tree is a good fit. Both algorithms operate in an on-line and incremental mode. This allows it to track the distribution of data as it arrives and changes over time. K-tree insertions and deletions allow flexibility when tracking data in volatile and changing collections. Furthermore, K-tree The following conditions were used when running the experiments. Experiments have been run to measure the quality dif- ference between various configurations of K-tree. Sec- tion 2.3 describes the modifications made to K-tree. Ta- ble 1 lists all the configurations tested. When document and link representations are com- bined they are both converted to unit vectors and con- catenated. Converting each representation to unit vec- tors ensures that the weights of one representation do not dominate the other. De Vries and Geva [5] found this to be effective for classification. The motivation behind this representation is that documents with similar content will link to similar documents. For example, in the current Wikipedia both car manufacturers BMW and Jaguar link to the Automotive Industry document. Link frequencies were weighted with the same Inverse Document Frequency heuristic from TF-IDF. The idea is to decrease the weight of highly frequent links and increase the weight of less frequent links. Links to year documents in the Wikipedia are examples of “stop links” that are weighted down by this heuristic. Unlike term frequencies in TF-IDF the link frequencies in LF-IDF are not normalised. De Vries and Geva [5] found that normalising link frequencies decreased classification performance. Links were represented using LF-IDF [5]. This re- sulted in a document-to-document link matrix. If there is a link between documents i and j then a value of one is added to position i, j and j, i in the matrix. If two documents both link to each other a value of two is recorded in their respective vectors. Each row vector of the matrix represents a document as a vector of link frequencies to and from other documents. Document content was represented with BM25 [17]. Stop words were removed and the remaining terms were stemmed using the Porter algorithm [16]. BM25 is determined by term distributions within each document and the entire collection. BM25 works with similar concepts as TF-IDF except that is has two tuning parameters. The BM25 tuning parameters were set to the same values as used for TREC [17], K 1 = 2 and b = 0 . 75 . K 1 influences the effect of term frequency and b influences document length. The INEX 2008 XML Mining collection was used to complete the experiments. It contains 114,366 docu- ments that are a subset of the XML Wikipedia corpus [8]. 15 different categories were provided for the docu- ments. performs best with dense vectors, such as those pro- duced by RI. 4 Document Representation 3.3 Random Indexing Example 3.4 Random Indexing K-tree 5 Experimental Setup