25th International Conference on Database Systems for Advanced Applications

Sep. 24-27, 2020, Jeju, South Korea

Click following URL

http://dasfaa2020.sigongji.com

to visit DASFAA 2020 Online Event Site

Paper details

Title: A Progrssive Approach for Computing the Earth Mover's Distance

Authors: Jiacheng Wu, Yong Zhang, Yu Chen and Chunxiao Xing

Abstract: Earth Mover's Distance (EMD) is defined as the minimum cost to transfer the components from one histogram to the other. As a robust similarity measurement, EMD has been widely adopted in many real world applications, like computer vision, machine learning and video identification. Since the time complexity of computing EMD is rather high, it is essential to devise effective techniques to boost the performance of EMD-based similarity search. In this paper, we focus on deducing a tighter lower bound of EMD, which still remains the bottleneck of applying EMD in real application scenarios. We devise an efficient approach to incrementally compute the EMD based on the primal-dual techniques from linear programming. Besides, we further propose progressive pruning techniques to eliminate the dissimilar results as well as enable early termination of the computation. We conduct extensive experiments on three real world datasets. The results show that our method achieves an order of magnitude performance gain than state-of-the-art approaches.

Video file:

Slide file:

Sponsors