Earth mover distance over high-dimensional spaces

ABSTRACT

The Earth Mover Distance (EMD) between two equal-size sets of points in ℝ^d is defined to be the minimum cost of a bipartite matching between the two pointsets. It is a natural metric for comparing sets of features, and as such, it has received significant interest in computer vision. Motivated by recent developments in that area, we address computational problems involving EMD over high-dimensional pointsets.

A natural approach is to embed the EMD metric into l₁, and use the algorithms designed for the latter space. However, Khot and Naor [KN06] show that any embedding of EMD over the d-dimensional Hamming cube into l₁ must incur a distortion Ω(d), thus practically losing all distance information. We circumvent this roadblock by focusing on sets with cardinalities upper-bounded by a parameter s, and achieve a distortion of only O(log s · log d). Since in applications the feature sets have bounded size, the resulting distortion is much smaller than the Ω(d) lower bound. Our approach is quite general and easily extends to EMD over ℝ^d.

We then provide a strong lower bound on the multi-round communicatic complexity of estimating EMD, which in particular strengthens the known non-embeddability result of [KN06]. Our bound exhibits a smooth tradeoff between approximation and communication, and for example implies that every algorithm that estimates EMD using constant size sketches can only achieve ω(log s) approximation.

REFERENCES

• 1: {AIK07} Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. Earth mover distance over high-dimensional spaces. ECCC Report TR07-048, May 2007.
• 2: Alexandr Andoni , Robert Krauthgamer, The Computational Hardness of Estimating Edit Distance [Extended Abstract], Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.724-734, October 21-23, 2007 [doi>10.1109/FOCS.2007.71]
• 3: Pankaj Agarwal , Kasturi Varadarajan, A near-linear constant-factor approximation for euclidean bipartite matching?, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997856]
• 4: Bo Brinkman , Moses Charikar, On the Impossibility of Dimension Reduction in \ell _1, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.514, October 11-14, 2003
• 5: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar, An information statistics approach to data stream and communication complexity, Journal of Computer and System Sciences, v.68 n.4, p.702-732, June 2004 [doi>10.1016/j.jcss.2003.11.006]
• 6: Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha , Serge Plotkin, Approximating a Finite Metric by a Small Number of Tree Metrics, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.379, November 08-11, 1998
• 7: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 8: {CK06} Moses Charikar and Robert Krauthgamer. Embedding the ulam metric into l₁. Theory of Computing, 2(11):207--224, 2006.
• 9: {CLJ⁺06} M. Charikar, C. Lv, W. Josephson, Z. Wang, and K. Li. Ferret: A toolkit for content-based similarity search. In Proceedings of ACM SIGOS EuroSys Conference, 2006. To appear.
• 10: Qin Lv , Moses Charikar , Kai Li, Image similarity search with compact data structures, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA [doi>10.1145/1031171.1031213]
• 11: Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, ACM Transactions on Algorithms (TALG), v.3 n.1, February 2007 [doi>10.1145/1186810.1186812]
• 12: {GD04} K. Grauman and T. Darrell. Fast contour matching using approximate Earth Mover's Distance. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Washington DC, June 2004.
• 13: Kristen Grauman , Trevor Darrell, Efficient Image Matching with Distributions of Local Invariant Features, Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) - Volume 2, p.627-634, June 20-26, 2005 [doi>10.1109/CVPR.2005.138]
• 14: Kristen Grauman , Trevor Darrell, The Pyramid Match Kernel: Discriminative Classification with Sets of Image Features, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1458-1465, October 17-20, 2005 [doi>10.1109/ICCV.2005.239]
• 15: {GD06a} K. Grauman and T. Darrell. Approximate correspondences in high dimensions. In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2006.
• 16: Kristen Grauman , Trevor Darrell, Unsupervised Learning of Categories from Sets of Partially Matching Image Features, Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.19-25, June 17-22, 2006 [doi>10.1109/CVPR.2006.322]
• 17: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 18: Piotr Indyk, A near linear time constant factor approximation for Euclidean bichromatic matching (cost), Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.39-42, January 07-09, 2007, New Orleans, Louisiana
• 19: Piotr Indyk, Uncertainty principles, extractors, and explicit embeddings of l2 into l1, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250881]
• 20: {IT03} P. Indyk and N. Thaper. Fast color image retrieval via embeddings. Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003.
• 21: {KN06} S. Khot and A. Naor. Nonembeddability theorems via fourier analysis. Mathematische Annalen, 334(4):821--852, 2006.
• 22: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
• 23: Robert Krauthgamer , Yuval Rabani, Improved lower bounds for embeddings into L₁, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1010-1017, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109669]
• 24: {Law76} E. Lawler. Combinatorial optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.
• 25: {LN04} J. Lee and A. Naor. Embedding the diamond graph in l_p and dimension reduction in l₁. Geometric and Functional Analysis (GAFA), 14(4):745--747, 2004.
• 26: S. Muthukrishnan , Süleyman Cenk Sahinalp, Approximate nearest neighbors and sequence comparison with block operations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.416-424, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335353]
• 27: Rafail Ostrovsky , Yuval Rabani, Low distortion embeddings for edit distance, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060623]
• 28: Rina Panigrahy, Entropy based nearest neighbor search in high dimensions, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1186-1195, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109688]
• 29: Yossi Rubner , Carlo Tomasi , Leonidas J. Guibas, The Earth Mover's Distance as a Metric for Image Retrieval, International Journal of Computer Vision, v.40 n.2, p.99-121, Nov. 2000 [doi>10.1023/A:1026543900054]
• 30: Michael Saks , Xiaodong Sun, Space lower bounds for distance approximation in the data stream model, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509963]
• 31: {Yao83} A. C-C. Yao. Lower bounds by probabilistic arguments. In Proceedings of the Symposium on Foundations of Computer Science, pages 420--428, 1983.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures; Pattern matching

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Design, Measurement