Embedding ultrametrics into low-dimensional spaces

ABSTRACT

We study the problem of minimum-distortion embedding of ultrametrics into the plane and higher dimensional spaces. Ultrametrics are a natural class of metrics that frequently occur in applications involving hierarchical clustering. Low-distortion embeddings of ultrametrics into the plane help visualizing complex structures they often represent.Given an ultrametric, a natural question is whether we can efficiently find an optimal-distortion embedding of this ultrametric into the plane, and if not, whether we can design an efficient algorithm that produces embeddings with near-optimal distortion. We show that the problem of finding minimum-distortion embedding of ultrametrics into the plane is NP-hard, and thus approximation algorithms are called for. Given an input ultrametric M, let c denote the minimum distortion achievable by any embedding of M into the plane. Our main result is a linear-time algorithm that produces an O(c³)-distortion embedding. This result can be generalized to embedding ultrametrics into R^d, for any d≥2, with distortion c^O(d), where c is the minimum distortion achievable for embedding the input ultrametric into R^d.Additionally, we show that any ultrametric can be embedded into the plane with distortion O(√n), and in general, into R^d with distortion d^O(1) n^1/d. Combining the two results together, we obtain an O(n^1/3)-approximation algorithm for the problem of minimum-distortion embedding of ultrametrics into the plane.

REFERENCES

• 1: Noga Alon , Mihai Bădoiu , Erik D. Demaine , Martin Farach-Colton , MohammadTaghi Hajiaghayi , Anastasios Sidiropoulos, Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 2: Robert Babilon , Jirí Matousek , Jana Maxová , Pavel Valtr, Low-Distortion Embeddings of Trees, Revised Papers from the 9th International Symposium on Graph Drawing, p.343-351, September 23-26, 2001
• 3: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 4: Yair Bartal , Manor Mendel, Dimension reduction for ultrametrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 5: Mihai Bǎdoiu , Julia Chuzhoy , Piotr Indyk , Anastasios Sidiropoulos, Low-distortion embeddings of general metrics into the line, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060624]
• 6: Mihai Bǎdoiu , Kedar Dhamdhere , Anupam Gupta , Yuri Rabinovich , Harald Räcke , R. Ravi , Anastasios Sidiropoulos, Approximation algorithms for low-distortion embeddings into low-dimensional spaces, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 7: M. Bǎdoiu, P. Indyk, and A. Sidiropoulos. A constant-factor approximation algorithm for embedding unweighted graphs into trees. AI Lab Technical Memo AIM-2004-015, 2004.
• 8: R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological sequence analysis. Cambridge University Press, 1998.
• 9: Yuval Emek , David Peleg, Approximating Minimum Max-Stretch spanning Trees on unweighted graphs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 10: David Eppstein , Kevin A. Wortman, Minimum dilation stars, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064142]
• 11: Martin Farach , Sampath Kannan, Efficient algorithms for inverting evolution, Journal of the ACM (JACM), v.46 n.4, p.437-449, July 1999 [doi>10.1145/320211.320212]
• 12: Anupam Gupta, Embedding tree metrics into low dimensional Euclidean spaces, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.694-700, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301434]
• 13: A. Gupta. Embedding trees into low dimensional euclidean spaces. Discrete and Computational Geometry, 24(1):105--116, 2000.
• 14: 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
• 15: Claire Kenyon , Yuval Rabani , Alistair Sinclair, Low distortion maps between point sets, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007398]
• 16: Joseph Y.-T. Leung , Tommy W. Tam , C. S. Wong , Gilbert H. Young , Francis Y.L. Chin, Packing squares into a square, Journal of Parallel and Distributed Computing, v.10 n.3, p.271-275, Nov. 1990 [doi>10.1016/0743-7315(90)90019-L]
• 17: N. Linial. Finite metric spaces - combinatorics, geometry and algorithms. Proceedings of the International Congress of Mathematicians III, pages 573--586, 2002.
• 18: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Proceedings of 35th Annual IEEE Symposium on Foundations of Computer Science, pages 577--591, 1994.
• 19: J. Matouǎek. Bi-lipschitz embeddings into low-dimensional euclidean spaces. Comment. Math. Univ. Carolinae, 31:589--600, 1990.
• 20: Christos Papadimitriou , Shmuel Safra, The complexity of low-distortion embeddings between point sets, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
approximation algorithms, embedding, ultrametrics