Low-complexity methods for assessing distances between pairs of documents

Abstract

Two sets Xand Xof histograms of words, and a vocabulary V are accessed. Each of the two sets is representable as a sparse matrix, each row of which corresponds to a histogram. Each histogram is representable as a sparse vector, whose dimension is determined by a dimension of the vocabulary. Two phases compute distances between pairs of histograms. The first phase includes computations performed for each histogram and for each word in the vocabulary to obtain a dense, floating-point vector y. The second phase includes computing, for each histogram, a sparse-matrix, dense-vector multiplication between a matrix-representation of the set Xof histograms and the vector y. The multiplication is performed to obtain distances between all histograms of the set Xand each histogram X[j]. Distances between all pairs of histograms are obtained, based on which distances between documents can subsequently be assessed.