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].