## 2 Background
[PERSON] [19] utilises an incremental version of the TF.IDF, whereby the term frequency of a word is determined based on the number of times the word appears until a particular time, and the number of times this same term appears in the newly appearing stories. After the documents' representations have been constructed, the next step would be that of finding the similarities between the different documents, and/or between the documents and clusters. According to [PERSON] [16], the similarity between 2 vectors can be calculated more precisely than by just a simple count of overlapping index terms. [PERSON] [8] defines two types of similarity measures, namely:Statistical Similarity--based on term and co-occurrence frequencies (e.g., using Cosine Similarity); and Semantic Similarity--using distance between terms meanings (e.g., using WordNet). In most cases, Cosine Similarity measure is used as the distance function [4, 4, 7, 8, 10, 14, 16, 17, 19, 20, 23, 26]. To enable the calculation of similarity between a document and a cluster, the cluster is usually represented using a centroid vector. The centroid vector is the weighted average of the documents within that cluster [4, 7, 17, 23]. [PERSON] [23] also cites the possibility of using median document weights rather than average document weights. In contrast, [PERSON] [17] describes a method to calculate the vector centroid based on the Rocchio algorithm. In this method, the centroid vector of a particular cluster is taken to be the sum of all the document vectors for positive training examples for that cluster subtracted by the sum of all the document vectors for negative training examples for that cluster. According to [PERSON] [3] and [PERSON] [4], similarity measures (or distance functions) are utilised by clustering methods in order to cluster documents in such a way that the intra-cluster similarity (the similarity between the documents within the same cluster) is maximised whilst the inter-cluster similarity is minimised. [PERSON] [23] divides clustering techniques into two types, namely:  
* **Hierarchical Clustering--**this technique produces hierarchies and is further split into:
* Agglomerative--whereby we start with each point being in a separate cluster, and at each step, the most similar pair of clusters are merged together (examples of a agglomerative hierarchical clustering algorithms may be found in [4, 19]), and
* Divisive--whereby we start with all the points being in a large single cluster, and at each step we split the cluster in order to maximise the intra-cluster similarity. * **Partitional Clustering--**whereby one level of partitioning of data points is created, such as the k-means Clustering. According to the literature reviewed in this research, the most common clustering method used is the k-means Clustering, or a variation of it. In k-means Clustering, we start with k points as the initial cluster centroids, and assign all the points to the nearest centroid. Then, a number of passes are made whereby the cluster centroid is recalculated and the cluster membership of each document is also recomputed [7, 12, 15, 16, 23, 26]. [PERSON] [15] adapts the k-means clustering algorithm for First Story Detection such that clustering is performed on incoming documents read from a stream. In this algorithm, each document is compared to existing clusters and is placed into a cluster if the cluster-document similarity exceeds a pre-defined threshold. Otherwise, the document is set to be the seed of a new cluster. Similar methods are also applied in [14, 20]. [PERSON] [14] further adapts the k-means clustering algorithm to First Story Detection in a resource-adaptive manner for large-scale processing scenarios. Less important documents are dropped from the main document queue and placed in a lower priority queue whenever the system becomes overloaded. The documents in the lower priority queue are then processed when more resources are available. The adaptation of clustering algorithms for incremental scenarios presents various problems.