Overcoming the l1 non-embeddability barrier: algorithms for product metrics

ABSTRACT

A common approach for solving computational problems over a difficult metric space is to embed the "hard" metric into L₁ which admits efficient algorithms and is thus considered an "easy" metric. This approach has proved successful or partially successful for important spaces such as the edit distance, but it also has inherent limitations: it is provably impossible to go below certain approximation for some metrics.

We propose a new approach, of embedding the difficult space into richer host spaces, namely iterated products of standard spaces like l₁ and l∞. We show that this class is rich since it contains useful metric spaces with only a constant distortion, and, at the same time, it is tractable and admits efficient algorithms. Using this approach, we obtain for example the first nearest neighbor data structure with O(log log d) approximation for edit distance in non-repetitive strings (the Ulam metric). This approximation is exponentially better than the lower bound for embedding into L₁. Furthermore, we give constant factor approximation for two other computational problems. Along the way, we answer positively a question posed in [Ajtai, Jayram, Kumar, and Sivakumar, STOC 2002]. One of our algorithms has already found applications for smoothed edit distance over 0--1 strings [Andoni and Krauthgamer, ICALP 2008].

REFERENCES

• 1: Nir Ailon , Bernard Chazelle , Seshadhri Comandur , Ding Liu, Estimating the distance to a monotone function, Random Structures & Algorithms, v.31 n.3, p.371-383, October 2007 [doi>10.1002/rsa.v31:3]
• 2: Miklós Ajtai , T. S. Jayram , Ravi Kumar , D. Sivakumar, Approximate counting of inversions in a data stream, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509964]
• 3: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 4: A. Andoni. Approximate nearest neighbor problem in high dimensions. M. Eng. Thesis, Massachusetts Institute of Technology, June 2005.
• 5: A. Andoni, K. Do Ba, and P. Indyk. Block heavy hitters. MIT Technical Report MIT-CSAIL-TR-2008-024, 2008.
• 6: Alexandr Andoni , Piotr Indyk, Efficient algorithms for substring near neighbor problem, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1203-1212, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109690]
• 7: Alexandr Andoni , Piotr Indyk , Robert Krauthgamer, Earth mover distance over high-dimensional spaces, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.343-352, January 20-22, 2008, San Francisco, California
• 8: 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]
• 9: Alexandr Andoni , Robert Krauthgamer, The Smoothed Complexity of Edit Distance, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part I, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70575-8_30]
• 10: Sanjeev Arora , James R. Lee , Assaf Naor, Euclidean distortion and the sparsest cut, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060673]
• 11: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 12: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 13: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 14: Tugkan Batu , Funda Ergün , Joe Kilian , Avner Magen , Sofya Raskhodnikova , Ronitt Rubinfeld , Rahul Sami, A sublinear algorithm for weakly approximating edit distance, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780590]
• 15: 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]
• 16: M. Charikar and R. Krauthgamer. Embedding the ulam metric into l₁. Theory of Computing, 2(11):207--224, 2006.
• 17: Edgar Chávez , Gonzalo Navarro , Ricardo Baeza-Yates , José Luis Marroquín, Searching in metric spaces, ACM Computing Surveys (CSUR), v.33 n.3, p.273-321, September 2001 [doi>10.1145/502807.502808]
• 18: Graham Cormode , S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, v.55 n.1, p.58-75, April 2005 [doi>10.1016/j.jalgor.2003.12.001]
• 19: Graham Cormode , S. Muthukrishnan, Space efficient mining of multigraph streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065201]
• 20: Nikhil R. Devanur , Subhash A. Khot , Rishi Saket , Nisheeth K. Vishnoi, Integrality gaps for sparsest cut and minimum linear arrangement problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132594]
• 21: Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Journal of Computer and System Sciences, v.60 n.3, p.717-751, June 2000 [doi>10.1006/jcss.1999.1692]
• 22: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 23: Parikshit Gopalan , T. S. Jayram , Robert Krauthgamer , Ravi Kumar, Estimating the sortedness of a data stream, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.318-327, January 07-09, 2007, New Orleans, Louisiana
• 24: S. Har-Peled, A Replacement for Voronoi Diagrams of Near Linear Size, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.94, October 14-17, 2001
• 25: Piotr Indyk, On approximate nearest neighbors under I norm, Journal of Computer and System Sciences, v.63 n.4, p.627-638, December 2001 [doi>10.1006/jcss.2001.1781]
• 26: P. Indyk, Algorithmic Applications of Low-Distortion Geometric Embeddings, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.10, October 14-17, 2001
• 27: Piotr Indyk, Approximate nearest neighbor algorithms for Frechet distance via product metrics, Proceedings of the eighteenth annual symposium on Computational geometry, p.102-106, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513414]
• 28: Piotr Indyk, Approximate Nearest Neighbor under edit distance via product metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 29: 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
• 30: P. Indyk and J. Matoušek. Discrete metric spaces. CRC Handbook of Discrete and Computational Geometry, 2nd edition, 2003.
• 31: 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]
• 32: P. Indyk and N. Thaper. Fast color image retrieval via embeddings. Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003.
• 33: Piotr Indyk , David Woodruff, Optimal approximations of the frequency moments of data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060621]
• 34: T. Jayram and D. Woodruff. Cascaded stream aggregates. Manuscript, 2008.
• 35: W. B. Johnson and J. Lindenstrauss, editors. Handbook of the geometry of Banach spaces. Vol. I. North-Holland Publishing Co., Amsterdam, 2001.
• 36: Subhash Khot , Assaf Naor, Nonembeddability theorems via Fourier analysis, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.101-112, October 23-25, 2005 [doi>10.1109/SFCS.2005.54]
• 37: Subhash A. Khot , Nisheeth K. Vishnoi, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into \ell 1, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.53-62, October 23-25, 2005 [doi>10.1109/SFCS.2005.74]
• 38: 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]
• 39: N. Linial. Finite metric spaces - combinatorics, geometry and algorithms. Proceedings of the International Congress of Mathematicians III, pages 573--586, 2002.
• 40: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.
• 41: J. I. Marden. Analyzing and Modeling Rank Data. Monographs on Statistics and Applied Probability 64. CRC Press, 1995.
• 42: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 43: Assaf Naor , Gideon Schechtman, Planar Earthmover is not in L_1, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.655-666, October 21-24, 2006 [doi>10.1109/FOCS.2006.60]
• 44: Rafail Ostrovsky , Yuval Rabani, Low distortion embeddings for edit distance, Journal of the ACM (JACM), v.54 n.5, p.23-es, October 2007 [doi>10.1145/1284320.1284322]
• 45: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms