Low distortion euclidean embeddings of trees View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1998-12

AUTHORS

Nathan Linial, Avner Magen, Michael E. Saks

ABSTRACT

We consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz constant as small as possible. We introduce the notationc2(X, d) for the least distortion with which the metric space (X, d) may be embedded in a Euclidean space. It is known that if (X, d) is a metric space withn points, thenc2(X, d)≤0(logn) and the bound is tight. LetT be a tree withn vertices, andd be the metric induced by it. We show thatc2(T, d)≤0(log logn), that is we provide an embeddingf of its vertices to the Euclidean space, such thatd(x, y)≤‖f(x)−f(y) ‖≤c log lognd(x, y) for some constantc. More... »

PAGES

339-348

References to SciGraph publications

  • 1986-06. The metrical interpretation of superreflexivity in banach spaces in ISRAEL JOURNAL OF MATHEMATICS
  • 1985-03. On lipschitz embedding of finite metric spaces in Hilbert space in ISRAEL JOURNAL OF MATHEMATICS
  • 1995-06. The geometry of graphs and some of its algorithmic applications in COMBINATORICA
  • 1986-06. On hilbertian subsets of finite metric spaces in ISRAEL JOURNAL OF MATHEMATICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf02773475

    DOI

    http://dx.doi.org/10.1007/bf02773475

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1021114518


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Applied Mathematics", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Institute of Computer Science, The Hebrew University of Jerusalem, 91904, Jerusalem, Israel", 
              "id": "http://www.grid.ac/institutes/grid.9619.7", 
              "name": [
                "Institute of Computer Science, The Hebrew University of Jerusalem, 91904, Jerusalem, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Linial", 
            "givenName": "Nathan", 
            "id": "sg:person.015760032537.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760032537.47"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institute of Computer Science, The Hebrew University of Jerusalem, 91904, Jerusalem, Israel", 
              "id": "http://www.grid.ac/institutes/grid.9619.7", 
              "name": [
                "Institute of Computer Science, The Hebrew University of Jerusalem, 91904, Jerusalem, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Magen", 
            "givenName": "Avner", 
            "id": "sg:person.016703157611.06", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016703157611.06"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Saks", 
            "givenName": "Michael E.", 
            "id": "sg:person.011520224512.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02776078", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002953231", 
              "https://doi.org/10.1007/bf02776078"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02766125", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045177033", 
              "https://doi.org/10.1007/bf02766125"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02801990", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038791459", 
              "https://doi.org/10.1007/bf02801990"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01200757", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015898290", 
              "https://doi.org/10.1007/bf01200757"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1998-12", 
        "datePublishedReg": "1998-12-01", 
        "description": "We consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz constant as small as possible. We introduce the notationc2(X, d) for the least distortion with which the metric space (X, d) may be embedded in a Euclidean space. It is known that if (X, d) is a metric space withn points, thenc2(X, d)\u22640(logn) and the bound is tight. LetT be a tree withn vertices, andd be the metric induced by it. We show thatc2(T, d)\u22640(log logn), that is we provide an embeddingf of its vertices to the Euclidean space, such thatd(x, y)\u2264\u2016f(x)\u2212f(y) \u2016\u2264c log lognd(x, y) for some constantc.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/bf02773475", 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136632", 
            "issn": [
              "0021-2172", 
              "1565-8511"
            ], 
            "name": "Israel Journal of Mathematics", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "106"
          }
        ], 
        "keywords": [
          "metric spaces", 
          "Euclidean space", 
          "finite metric spaces", 
          "embeddings of trees", 
          "space", 
          "vertices", 
          "Lipschitz", 
          "constantc", 
          "least distortion", 
          "problem", 
          "embedding", 
          "distortion", 
          "Lett", 
          "low distortion", 
          "andd", 
          "metrics", 
          "point", 
          "logs", 
          "trees"
        ], 
        "name": "Low distortion euclidean embeddings of trees", 
        "pagination": "339-348", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1021114518"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf02773475"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf02773475", 
          "https://app.dimensions.ai/details/publication/pub.1021114518"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-09-02T15:49", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_286.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/bf02773475"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf02773475'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf02773475'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02773475'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02773475'


     

    This table displays all metadata directly associated to this object as RDF triples.

    113 TRIPLES      21 PREDICATES      49 URIs      36 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf02773475 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 anzsrc-for:0102
    4 schema:author N3a49d4f2b1ff43ecb025fe38d92ae6f7
    5 schema:citation sg:pub.10.1007/bf01200757
    6 sg:pub.10.1007/bf02766125
    7 sg:pub.10.1007/bf02776078
    8 sg:pub.10.1007/bf02801990
    9 schema:datePublished 1998-12
    10 schema:datePublishedReg 1998-12-01
    11 schema:description We consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz constant as small as possible. We introduce the notationc2(X, d) for the least distortion with which the metric space (X, d) may be embedded in a Euclidean space. It is known that if (X, d) is a metric space withn points, thenc2(X, d)≤0(logn) and the bound is tight. LetT be a tree withn vertices, andd be the metric induced by it. We show thatc2(T, d)≤0(log logn), that is we provide an embeddingf of its vertices to the Euclidean space, such thatd(x, y)≤‖f(x)−f(y) ‖≤c log lognd(x, y) for some constantc.
    12 schema:genre article
    13 schema:isAccessibleForFree true
    14 schema:isPartOf N291ba12f1f9d434396f3700e32c5d2ae
    15 N4d4cb4e96b50473781930a75ec40750d
    16 sg:journal.1136632
    17 schema:keywords Euclidean space
    18 Lett
    19 Lipschitz
    20 andd
    21 constantc
    22 distortion
    23 embedding
    24 embeddings of trees
    25 finite metric spaces
    26 least distortion
    27 logs
    28 low distortion
    29 metric spaces
    30 metrics
    31 point
    32 problem
    33 space
    34 trees
    35 vertices
    36 schema:name Low distortion euclidean embeddings of trees
    37 schema:pagination 339-348
    38 schema:productId Na2faab0d8f284fa694125fd89b11e2a7
    39 Nad38d598e2554b44838a1e421a9d5459
    40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021114518
    41 https://doi.org/10.1007/bf02773475
    42 schema:sdDatePublished 2022-09-02T15:49
    43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    44 schema:sdPublisher Ne020ff60fc67445abaf57f8435dbc7b1
    45 schema:url https://doi.org/10.1007/bf02773475
    46 sgo:license sg:explorer/license/
    47 sgo:sdDataset articles
    48 rdf:type schema:ScholarlyArticle
    49 N291ba12f1f9d434396f3700e32c5d2ae schema:volumeNumber 106
    50 rdf:type schema:PublicationVolume
    51 N3a49d4f2b1ff43ecb025fe38d92ae6f7 rdf:first sg:person.015760032537.47
    52 rdf:rest N470e6cf0f9c849469a2d2a25707875ec
    53 N470e6cf0f9c849469a2d2a25707875ec rdf:first sg:person.016703157611.06
    54 rdf:rest N829a7a83ff3a484885803edb4a8cc79e
    55 N4d4cb4e96b50473781930a75ec40750d schema:issueNumber 1
    56 rdf:type schema:PublicationIssue
    57 N829a7a83ff3a484885803edb4a8cc79e rdf:first sg:person.011520224512.05
    58 rdf:rest rdf:nil
    59 Na2faab0d8f284fa694125fd89b11e2a7 schema:name doi
    60 schema:value 10.1007/bf02773475
    61 rdf:type schema:PropertyValue
    62 Nad38d598e2554b44838a1e421a9d5459 schema:name dimensions_id
    63 schema:value pub.1021114518
    64 rdf:type schema:PropertyValue
    65 Ne020ff60fc67445abaf57f8435dbc7b1 schema:name Springer Nature - SN SciGraph project
    66 rdf:type schema:Organization
    67 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Mathematical Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Pure Mathematics
    72 rdf:type schema:DefinedTerm
    73 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Applied Mathematics
    75 rdf:type schema:DefinedTerm
    76 sg:journal.1136632 schema:issn 0021-2172
    77 1565-8511
    78 schema:name Israel Journal of Mathematics
    79 schema:publisher Springer Nature
    80 rdf:type schema:Periodical
    81 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
    82 schema:familyName Saks
    83 schema:givenName Michael E.
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
    85 rdf:type schema:Person
    86 sg:person.015760032537.47 schema:affiliation grid-institutes:grid.9619.7
    87 schema:familyName Linial
    88 schema:givenName Nathan
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760032537.47
    90 rdf:type schema:Person
    91 sg:person.016703157611.06 schema:affiliation grid-institutes:grid.9619.7
    92 schema:familyName Magen
    93 schema:givenName Avner
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016703157611.06
    95 rdf:type schema:Person
    96 sg:pub.10.1007/bf01200757 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015898290
    97 https://doi.org/10.1007/bf01200757
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/bf02766125 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045177033
    100 https://doi.org/10.1007/bf02766125
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/bf02776078 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002953231
    103 https://doi.org/10.1007/bf02776078
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/bf02801990 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038791459
    106 https://doi.org/10.1007/bf02801990
    107 rdf:type schema:CreativeWork
    108 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA
    109 schema:name Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA
    110 rdf:type schema:Organization
    111 grid-institutes:grid.9619.7 schema:alternateName Institute of Computer Science, The Hebrew University of Jerusalem, 91904, Jerusalem, Israel
    112 schema:name Institute of Computer Science, The Hebrew University of Jerusalem, 91904, Jerusalem, Israel
    113 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...