The Earth Mover's Distance (EMD) is a state-of-the art metric for comparingprobability distributions. The high distinguishability offered by the EMD comesat a high cost in computational complexity. Therefore, linear-complexityapproximation algorithms have been proposed to improve its scalability.However, these algorithms are either limited to vector spaces with only a fewdimensions or require the probability distributions to populate the vectorspace sparsely. We propose novel approximation algorithms that overcome both ofthese limitations, yet still achieve linear time complexity. All our algorithmsare data parallel, and therefore, we can take advantage of massively parallelcomputing engines, such as Graphics Processing Units (GPUs). The experiments onMNIST images show that the new algorithms can perform a billion distancecomputations in less than a minute using a single GPU. On the populartext-based 20 Newsgroups dataset, the new algorithms are four orders ofmagnitude faster than the state-of-the-art FastEMD library and match its searchaccuracy.