In many domains, the similarity between two images depends on the spatial locations of their features. The earth mover's distance (EMD), first proposed by Werman et al. [8], measures such similarity. It yields higher-quality image retrieval results than the Lp-norm, quadratic-form distance, and Jeffrey divergence [6], and has also been used for similarity search on contours [3], melodies [7], and graphs [2]. Computing the EMD is an expensive linearprogramming problem: It takes 41 s to compute the EMD between 12-dimensional features extracted from images partitioned into 8 12 tiles, so searching a database of 4,000 images can take 46 h. In this paper, we redefine the EMD to work with multidimensional feature vectors, and show how the computation can be performed separately for each dimension. We then develop lower bounds that are reasonably tight and can be computed quickly. A multi-resolution indexing scheme based on either sequential scan or the M-tree [1] can answer similarity queries more than 500 times faster by combining the two techniques.