Linear-Complexity Relaxed Word Mover's Distance with GPU Acceleration

摘要

The amount of unstructured text-based data is growing every day. Querying,clustering, and classifying this big data requires similarity computationsacross large sets of documents. Whereas low-complexity similarity metrics areavailable, attention has been shifting towards more complex methods thatachieve a higher accuracy. In particular, the Word Mover's Distance (WMD)method proposed by Kusner et al. is a promising new approach, but its timecomplexity grows cubically with the number of unique words in the documents.The Relaxed Word Mover's Distance (RWMD) method, again proposed by Kusner etal., reduces the time complexity from qubic to quadratic and results in alimited loss in accuracy compared with WMD. Our work contributes alow-complexity implementation of the RWMD that reduces the average timecomplexity to linear when operating on large sets of documents. Ourlinear-complexity RWMD implementation, henceforth referred to as LC-RWMD, mapswell onto GPUs and can be efficiently distributed across a cluster of GPUs. Ourexperiments on real-life datasets demonstrate 1) a performance improvement oftwo orders of magnitude with respect to our GPU-based distributedimplementation of the quadratic RWMD, and 2) a performance improvement of threeto four orders of magnitude with respect to our distributed WMD implementationthat uses GPU-based RWMD for pruning.