Multidimensional distributions are often used in data mining to describe and summarize different features of large datasets. It is natural to look for distinct classes in such datasets by clustering the data. A common approach entails the use of methods like k-means clustering. However, the k-means method inherently relies on the Euclidean metric in the embedded space and does not account for additional topology underlying the distribution.In this paper, we propose using Earth Mover Distance (EMD) to compare multidimensional distributions. For a n-bin histogram, the EMD is based on a solution to the transportation problem with time complexity O(n3 log n). To mitigate the high computational cost of EMD, we propose an approximation that reduces the cost to linear time. Given the large size of our dataset a fast approximation is crucial for this application.Other notions of distances such as the information theoretic Kullback-Leibler divergence and statistical χ2 distance, account only for the correspondence between bins with the same index, and do not use information across bins, and are sensitive to bin size. A cross-bin distance measure like EMD is not affected by binning differences and meaningfully matches the perceptual notion of "nearness".Our technique is simple, efficient and practical for clustering distributions. We demonstrate the use of EMD on a real-world application of analyzing 411,550 anonymous mobility usage patterns which are defined as distributions over a manifold. EMD allows us to represent inherent relationships in this space, and enables us to successfully cluster even sparse signatures.