Earth Mover’s Distance based Similarity Search at Scale

Earth Mover’s Distance (EMD), as a similarity measure, has re-ceived a lot of attention in the fields of multimedia and probabilis-tic databases, computer vision, image retrieval, machine learning, etc. EMD on multidimensional histograms provides better distin-guishability between the objects approximated by the histograms (e.g., images), compared to classic measures like Euclidean dis-tance. Despite its usefulness, EMD has a high computational cost; therefore, a number of effective filtering methods have been pro-posed, to reduce the pairs of histograms for which the exact EMD has to be computed, during similarity search. Still, EMD calcu-lations in the refinement step remain the bottleneck of the whole similarity search process. In this paper, we focus on optimizing the refinement phase of EMD-based similarity search by (i) adapting an efficient min-cost flow algorithm (SIA) for EMD computation, (ii) proposing a dynamic distance bound, which can be used to ter-minate an EMD refinement early, and (iii) proposing a dynamic re-finement order for the candidates which, paired with a concurrent EMD refinement strategy, reduces the amount of needless compu-tations. Our proposed techniques are orthogonal to and can be eas-ily integrated with the state-of-the-art filtering techniques, reducing the cost of EMD-based similarity queries by orders of magnitude. 1