Online Document Clustering Using the GPU
Benjamin E. Teitler, Jagan Sankaranarayanan, Hanan Samet, Marco Adelfio · 2014
Online document clustering takes as its input a list of document vectors, ordered by time. A document vector consists of a list of K terms and their associated weights. The generation of terms and their weights from the document text may vary, but the TF-IDF (term frequency-inverse document frequency) method is popular for clustering applications [1]. The assumption is that the resulting document vector is a good overall representation of the original document. We note that the dimensionality of the document vectors is very high (potentially infinite), since a document could potentially contain any word (term). We also note that the vectors are sparse in the sense that most term weights have a zero value. We assume that each term not explicitly present in a particular document vector has a weight of zero. Document vectors are normalized. Clusters are also represented as a list of weighted terms. At any given time, a cluster’s term vector is equal to the average of all the document vector’s contained by the cluster. Cluster term vectors are truncated to the top K terms (those containing the highest term weights). Cluster term vectors are kept normalized. The objective of the algorithm is to partition the set of document vectors into a set of clusters, each cluster containing only those documents which are similar to each other with respect to some metric. For this paper, we consider the Euclidean dot product as the similarity metric, as it has been shown to provide good results with the TF-IDF metric [1]. The similarity between a cluster and a document is defined as the dot product between their term vectors. We first present serial a algorithm for online clustering. We then describe a PRAM algorithm for parallel online clustering, assuming a CRCW model. Finally, we present a practical implementation of an approximate parallel online clustering algorithm, suitable for the CUDA parallel computing architecture [2]. 1. Serial Clustering 1 The basic serial online clustering algorithm takes as input a list of n document vectors, as well as a clustering threshold T ranging between 0 and 1. Below is a high level overview of the algorithm.