Embedding tree metrics into low dimensional Euclidean spaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Embedding tree metrics into low dimensional Euclidean spaces

Full text

Pdf (557 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-first annual ACM symposium on Theory of computing table of contents

Atlanta, Georgia, United States

Pages: 694 - 700

Year of Publication: 1999

ISBN:1-58113-067-8

Author

Anupam Gupta

Computer Science Division, University of California, Berkeley, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 42, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301250.301434 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Juan Arias-de-Reyna and Luis Rodrfguez-Piazza. Finite metric spaces needing high dimension for Lipschitz embeddings into Banach spaces. Israel d. of Math., 79(1):103-113, 1992.
	2	Jean Bourgain. The metrical interpretation of superrefiexivity in Banach spaces. Israel J. of Math., 56(2):222-230, 1986.
	3	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
	4	J. H. Conway , N. J. A. Sloane , E. Bannai, Sphere-packings, lattices, and groups, Springer-Verlag New York, Inc., New York, NY, 1987
	5	Michel Marie Deza and Monique Laurent. Geometry of Cuts and Metrics. Springer Verlag, 1997.
	6	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]
	7	William B. Johnson and Joram Lindenstrauss. Ex~ tensions of Lipschitz maps into a Hilbert space. Contemporary Mathematics, 26:189-206, 1984.
	8	Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215-245~ 1995. (Preliminary version in: 35th Annual Symposium on Foundations of Computer Science, pages 577- 59t, 1994.).
	9	Nathan Linial , Avner Magen , Michael E. Saks, Trees and Euclidean metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.169-175, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276726]
	10	Ji~i Matou~ek. Bi-Lipschitz embeddings into low dimensional Euclidean spaces. Comment. Math. Univ. Carolinae, 31:589-600, 1990.
	11	Jifi Matou~ek. On the distortion required for embedding finite metric spaces into normed spaces. Israel J. of Math., 93:333-344, 1996.
	12	Ji~i Matou~ek. On embedding trees into uniformly convex Banach spaces. Israel J. of Math., To appear, 1998. (Czech version in: Lipschitz distance of metric spaces, C.Sc. degree thesis, Charles University, 1990).

CITED BY 6

	Anupam Gupta, Improved bandwidth approximation for trees, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.788-793, January 09-11, 2000, San Francisco, California, United States
	M. Fatih Demirci , Ali Shokoufandeh , Yakov Keselman , Lars Bretzner , Sven Dickinson, Object Recognition as Many-to-Many Feature Matching, International Journal of Computer Vision, v.69 n.2, p.203-222, August 2006
	Mihai Bǎdoiu , Julia Chuzhoy , Piotr Indyk , Anastasios Sidiropou, Embedding ultrametrics into low-dimensional spaces, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Eng Keong Lua , Timothy Griffin , Marcelo Pias , Han Zheng , Jon Crowcroft, On the accuracy of embeddings for internet coordinate systems, Proceedings of the Internet Measurement Conference 2005 on Internet Measurement Conference, p.11-11, October 19-21, 2005, Berkeley, CA
	Bai Xiao , Andrea Torsello , Edwin R. Hancock, Isotree: Tree clustering via metric embedding, Neurocomputing, v.71 n.10-12, p.2029-2036, June, 2008
	Claire Mathieu , Charalampos Papamanthou, Distortion lower bounds for line embeddings, Information Processing Letters, v.108 n.4, p.175-178, October, 2008