Article

Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics

Authors:

Erik D. Demaine,

Martin Farach-Colton,

MohammadTaghi Hajiaghayi,

Anastasios SidiropoulosAuthors Info & Claims

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 650 - 659

Published: 23 January 2005 Publication History

Abstract

We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the relative order between pairs of distances, and not the distances themselves, that must be preserved as much as possible. The (multiplicative) relaxation of an ordinal embedding is the maximum ratio between two distances whose relative order is inverted by the embedding. We develop several worst-case bounds and approximation algorithms on ordinal embedding. In particular, we establish that ordinal embedding has many qualitative differences from metric embedding, and capture the ordinal behavior of ultrametrics and shortest-path metrics of unweighted trees.

References

[1]

R. Agarwala, V. Bafna, M. Farach, M. Paterson, and M. Thorup. On the approximability of numerical taxonomy (fitting distances by tree metrics), SIAM J. Comput., 28 (1999), pp. 1073--1085.

Digital Library

[2]

N. Alon, Tools from higher algebra, in Handbook of combinatorics, R. L. Graham, M. Grötschel, and L. Lovász, eds., vol. 2, MIT Press, 1995, ch. 32, pp. 1749--1783.

Digital Library

[3]

N. Alon, P. Frankl, and V. Rödl, Geometrical realization of set systems and probabilistic communication complexity, in Proceedings of the 26th Annual Symposium on Foundations of Computer Science, Portland, 1985, pp. 277--280.

[4]

R. Babilon, J. Matoušek, J. Maxová, and P. Valtr, Low-distortion embeddings of trees. Journal of Graph Algorithms and Applications, 7 (2003), pp. 399--409.

[5]

M. Bădoiu, K. Dhamdhere, A. Gupta, Y. Rabinovich, H. Raecke, R. Ravi, and A. Sidiropoulos, Approximation algorithms for low-distortion embeddings into low-dimensional spaces, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, 2005.

Digital Library

[6]

Y. Bartal and M. Mendel, Dimension reduction for ultrametrics, in Proceedings of the 15th ACM-SIAM Symp. on Discrete Algorithms, 2004, pp. 664--665.

Digital Library

[7]

Y. Bilu and N. Linial, Monotone maps, sphericity and bounded second eigenvalue. arXiv:math.CO/0401293, 2004.

[8]

J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math., 52 (1985), pp. 46--52.

[9]

B. Brinkman and M. Charikar, On the impossibility of dimension reduction in l1, in Proc. of the 44th Symposium on Foundations of Computer Science, 2003, pp. 514--523.

Digital Library

[10]

M. Bădoiu, Approximation algorithm for embedding metrics into a two-dimensional space, in Procedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 2003, pp. 434--443.

Digital Library

[11]

M. Bădoiu, E. D. Demaine, M. Hajiaghayi, and P. Indyk. Low-dimensional embedding with extra information, in Proceedings of the 20th Annual ACM Symposium on Computational Geometry, Brooklyn, New York, June 2004.

Digital Library

[12]

B. Chor and M. Sudan, A geometric approach to betweennes, SIAM J. Discrete Math., 11 (1998), pp. 511--523.

Digital Library

[13]

J. P. Cunningham and R. N. Shepard, Monotone mapping of similarities into a general metric space. Journal of Mathematical Psychology, 11 (1974), pp. 335--364.

[14]

P. Erdös and H. Sachs, Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 12 (1963), pp. 251--257.

[15]

M. Farach and S. Kannan, Efficient algorithms for inverting evolution, J. ACM, 46 (1999), pp. 437--449.

Digital Library

[16]

M. Farach, S. Kannan, and T. Warnow. A robust model for finding optimal evolutionary trees, Algorithmica, 13 (1995), pp. 155--179.

[17]

A. Gupta, Embedding tree metrics into low-dimensional Euclidean spaces, Discrete Comput. Geom., 24:105--116 (2000).

[18]

E. F. Harding, The number of partitions of a set of N points in k dimensions induced by hyperplanes, Proceedings of the Edinburgh Mathematical Society, Series II, 15 (1966/1967), pp. 285--289.

[19]

J. Håstad, L. Ivansson, and J. Lagergren, Fitting points on the real line and its application to RH mapping, Journal of Algorithms, 49 (2003), pp. 42--62.

Digital Library

[20]

W. Holman, The relation between hierarchical and euclidean models for psychological distances, Psychometrika, 37 (1972), pp. 417--423.

[21]

P. Indyk and J. Matoušek, Low-distortion embeddings of finite metric spaces, in Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O'Rourke, eds., CRC Press, second ed., 2004, ch. 8, pp. 177--196.

[22]

L. Ivansson, Computational Aspects of Radiation Hybrid, PhD thesis, Royal Institute of Technology, 2000.

[23]

W. B. Johnson and J. Lindenstrauss, Extensions of lipshitz mapping into hilbert space, Contemporary Mathematics, 26 (1984), pp. 189--206.

[24]

J. B. Kruskal, Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis, Psychometrika, 29 (1964), pp. 1--28.

[25]

J. B. Kruskal, Non-metric multidimensional scaling, Psychometrika, 29 (1964), pp. 115--129.

[26]

J. R. Lee and A. Naor, Embedding the diamond graph in Lp and dimension reduction in L1, Geometric and Functional Analysis, 14 (2004), pp. 745--747.

[27]

N. Linial, E. London, and Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica, 15 (1995), pp. 215--245.

[28]

J. Matoušek, On embedding expanders into lp spaces, Israel Journal of Mathematics, 102 (1997), pp. 189--197.

[29]

J. Opatrny, Total ordering problem, SIAM J. Computing, 8 (1979), pp. 111--114.

[30]

R. Shah and M. Farach-Colton, On the complexity of ordinal clustering, Journal of Classification (2004). To appear.

[31]

R. N. Shepard, Multidimensional scaling with unknown distance function I, Psychometrika, 27 (1962), pp. 125--140.

[32]

W. S. Torgerson, Multidimensional scaling I: Theory and method, Psychometrika, 17 (1952), pp. 401--414.

[33]

H. E. Warren, Lower bounds for approximation by nonlinear manifolds, Trans. Amer. Math. Soc., 133:167--178 (1968).

Cited By

Bǎdoiu MIndyk PSidiropoulos AGabow H(2007)Approximation algorithms for embedding general metrics into treesProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1283383.1283438(512-521)Online publication date: 7-Jan-2007
https://dl.acm.org/doi/10.5555/1283383.1283438
Kleinberg R(2007)Geographic Routing Using Hyperbolic SpaceProceedings of the IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications10.1109/INFCOM.2007.221(1902-1909)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.1109/INFCOM.2007.221
Bǎdoiu MChuzhoy JIndyk PSidiropou AAmenta NCheong O(2006)Embedding ultrametrics into low-dimensional spacesProceedings of the twenty-second annual symposium on Computational geometry10.1145/1137856.1137886(187-196)Online publication date: 5-Jun-2006
https://dl.acm.org/doi/10.1145/1137856.1137886
Show More Cited By

Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation

Recommendations

Ordinal embeddings of minimum relaxation: General properties, trees, and ultrametrics

We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the relative order between pairs of distances, and not the ...
Computational metric embeddings
Anti-forensic Steganography Using Multi-bit Minimum Error Replacement with Flexible Bit Location
IS3C '12: Proceedings of the 2012 International Symposium on Computer, Consumer and Control

Multi-bit minimum error replacement (MER) is a method that can embed multi-bit logo/secret data into k least-significant bits (LSBs) of cover data only introduces minimum embedding error (MEE). However, k-LSBs MER suffers from weak anti-forensics. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '05: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms

January 2005

1205 pages

ISBN:0898715857

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2005

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
230
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bǎdoiu MIndyk PSidiropoulos AGabow H(2007)Approximation algorithms for embedding general metrics into treesProceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1283383.1283438(512-521)Online publication date: 7-Jan-2007
https://dl.acm.org/doi/10.5555/1283383.1283438
Kleinberg R(2007)Geographic Routing Using Hyperbolic SpaceProceedings of the IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications10.1109/INFCOM.2007.221(1902-1909)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.1109/INFCOM.2007.221
Bǎdoiu MChuzhoy JIndyk PSidiropou AAmenta NCheong O(2006)Embedding ultrametrics into low-dimensional spacesProceedings of the twenty-second annual symposium on Computational geometry10.1145/1137856.1137886(187-196)Online publication date: 5-Jun-2006
https://dl.acm.org/doi/10.1145/1137856.1137886
Cary MRudra ASabharwal A(2005)On the hardness of embeddings between two finite metricsProceedings of the 32nd international conference on Automata, Languages and Programming10.1007/11523468_114(1412-1423)Online publication date: 11-Jul-2005
https://dl.acm.org/doi/10.1007/11523468_114

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents