Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2008

AUTHORS

Saverio Caminiti , Irene Finocchi , Rossella Petreschi

ABSTRACT

We address the problem of labeling the nodes of a tree such that one can determine the identifier of the least common ancestor of any two nodes by looking only at their labels. This problem has application in routing and in distributed computing in peer-to-peer networks. A labeling scheme using Θ(log2n)-bit labels has been previously presented by Peleg. By engineering this scheme, we obtain a variety of data structures with the same asymptotic performances. We conduct a thorough experimental evaluation of all these data structures. Our results clearly show which variants achieve the best performances in terms of space usage, construction time, and query time. More... »

PAGES

234-245

References to SciGraph publications

  • 2000. Informative Labeling Schemes for Graphs in MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2000
  • 2006. Short Labels by Traversal and Jumping in STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY
  • 1999. Proximity-Preserving Labeling Schemes and Their Applications in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • Book

    TITLE

    Algorithms - ESA 2008

    ISBN

    978-3-540-87743-1
    978-3-540-87744-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-87744-8_20

    DOI

    http://dx.doi.org/10.1007/978-3-540-87744-8_20

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Computer Science Department, Sapienza University of Rome, Via Salaria, 113, 00198, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Caminiti", 
            "givenName": "Saverio", 
            "id": "sg:person.010013323122.87", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Computer Science Department, Sapienza University of Rome, Via Salaria, 113, 00198, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Finocchi", 
            "givenName": "Irene", 
            "id": "sg:person.014240412541.72", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Computer Science Department, Sapienza University of Rome, Via Salaria, 113, 00198, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Petreschi", 
            "givenName": "Rossella", 
            "id": "sg:person.011402427702.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-46784-x_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003259743", 
              "https://doi.org/10.1007/3-540-46784-x_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/564870.564914", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009882975"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/62212.62244", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022515096"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11780823_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032547776", 
              "https://doi.org/10.1007/11780823_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11780823_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032547776", 
              "https://doi.org/10.1007/11780823_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44612-5_53", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032559164", 
              "https://doi.org/10.1007/3-540-44612-5_53"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-247x(67)90082-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040665844"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2007.03.009", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053662883"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.1966.1053860", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061646188"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539700370539", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879236"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539703433912", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879473"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0097539703437211", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062879498"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0895480103433409", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062882719"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008", 
        "datePublishedReg": "2008-01-01", 
        "description": "We address the problem of labeling the nodes of a tree such that one can determine the identifier of the least common ancestor of any two nodes by looking only at their labels. This problem has application in routing and in distributed computing in peer-to-peer networks. A labeling scheme using \u0398(log2n)-bit labels has been previously presented by Peleg. By engineering this scheme, we obtain a variety of data structures with the same asymptotic performances. We conduct a thorough experimental evaluation of all these data structures. Our results clearly show which variants achieve the best performances in terms of space usage, construction time, and query time.", 
        "editor": [
          {
            "familyName": "Halperin", 
            "givenName": "Dan", 
            "type": "Person"
          }, 
          {
            "familyName": "Mehlhorn", 
            "givenName": "Kurt", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-87744-8_20", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-87743-1", 
            "978-3-540-87744-8"
          ], 
          "name": "Algorithms - ESA 2008", 
          "type": "Book"
        }, 
        "name": "Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors", 
        "pagination": "234-245", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-87744-8_20"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a88f3b3e4ba1ddebed256c83bb876716da4bfecefdd4a6b2f160d012b13e2492"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1035385068"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-87744-8_20", 
          "https://app.dimensions.ai/details/publication/pub.1035385068"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T06:09", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000350_0000000350/records_77554_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-87744-8_20"
      }
    ]
     

    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/978-3-540-87744-8_20'

    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/978-3-540-87744-8_20'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-87744-8_20'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-87744-8_20'


     

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

    123 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-87744-8_20 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nae2a3c85cdca445292187c89b500686b
    4 schema:citation sg:pub.10.1007/11780823_12
    5 sg:pub.10.1007/3-540-44612-5_53
    6 sg:pub.10.1007/3-540-46784-x_5
    7 https://doi.org/10.1016/0022-247x(67)90082-0
    8 https://doi.org/10.1016/j.tcs.2007.03.009
    9 https://doi.org/10.1109/tit.1966.1053860
    10 https://doi.org/10.1137/s0097539700370539
    11 https://doi.org/10.1137/s0097539703433912
    12 https://doi.org/10.1137/s0097539703437211
    13 https://doi.org/10.1137/s0895480103433409
    14 https://doi.org/10.1145/564870.564914
    15 https://doi.org/10.1145/62212.62244
    16 schema:datePublished 2008
    17 schema:datePublishedReg 2008-01-01
    18 schema:description We address the problem of labeling the nodes of a tree such that one can determine the identifier of the least common ancestor of any two nodes by looking only at their labels. This problem has application in routing and in distributed computing in peer-to-peer networks. A labeling scheme using Θ(log2n)-bit labels has been previously presented by Peleg. By engineering this scheme, we obtain a variety of data structures with the same asymptotic performances. We conduct a thorough experimental evaluation of all these data structures. Our results clearly show which variants achieve the best performances in terms of space usage, construction time, and query time.
    19 schema:editor Nf1aa5e0c121c4827a41fa1ccfbdf0eb6
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree false
    23 schema:isPartOf N061d580e249a499d9172b5902b3f3b94
    24 schema:name Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors
    25 schema:pagination 234-245
    26 schema:productId N24ab0dca38604ef8a21fb251bc54e330
    27 N4fccb040c2ed418bb2af6cff215574ef
    28 Nade35645d714442f9ec6caa157ad5c72
    29 schema:publisher Nb6ab95f0c62e4ff0b6e417061c645a98
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035385068
    31 https://doi.org/10.1007/978-3-540-87744-8_20
    32 schema:sdDatePublished 2019-04-16T06:09
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher N75b13a7b0a694befa9d7fc3b2b8677df
    35 schema:url https://link.springer.com/10.1007%2F978-3-540-87744-8_20
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N00117e9576684ba58a7b13b15b5064a4 rdf:first sg:person.011402427702.78
    40 rdf:rest rdf:nil
    41 N061d580e249a499d9172b5902b3f3b94 schema:isbn 978-3-540-87743-1
    42 978-3-540-87744-8
    43 schema:name Algorithms - ESA 2008
    44 rdf:type schema:Book
    45 N24ab0dca38604ef8a21fb251bc54e330 schema:name doi
    46 schema:value 10.1007/978-3-540-87744-8_20
    47 rdf:type schema:PropertyValue
    48 N4fccb040c2ed418bb2af6cff215574ef schema:name readcube_id
    49 schema:value a88f3b3e4ba1ddebed256c83bb876716da4bfecefdd4a6b2f160d012b13e2492
    50 rdf:type schema:PropertyValue
    51 N75b13a7b0a694befa9d7fc3b2b8677df schema:name Springer Nature - SN SciGraph project
    52 rdf:type schema:Organization
    53 N809953b6fc734934b7b5c7ec8f6d09cd rdf:first sg:person.014240412541.72
    54 rdf:rest N00117e9576684ba58a7b13b15b5064a4
    55 N894f1c285847426aada2beb263cd09d4 schema:familyName Halperin
    56 schema:givenName Dan
    57 rdf:type schema:Person
    58 Nade35645d714442f9ec6caa157ad5c72 schema:name dimensions_id
    59 schema:value pub.1035385068
    60 rdf:type schema:PropertyValue
    61 Nae2a3c85cdca445292187c89b500686b rdf:first sg:person.010013323122.87
    62 rdf:rest N809953b6fc734934b7b5c7ec8f6d09cd
    63 Nb498a5cfe42d4162a47e65272a3a4cc4 rdf:first Nf12006d2af2444ab84f84a7b719349d5
    64 rdf:rest rdf:nil
    65 Nb6ab95f0c62e4ff0b6e417061c645a98 schema:location Berlin, Heidelberg
    66 schema:name Springer Berlin Heidelberg
    67 rdf:type schema:Organisation
    68 Nf12006d2af2444ab84f84a7b719349d5 schema:familyName Mehlhorn
    69 schema:givenName Kurt
    70 rdf:type schema:Person
    71 Nf1aa5e0c121c4827a41fa1ccfbdf0eb6 rdf:first N894f1c285847426aada2beb263cd09d4
    72 rdf:rest Nb498a5cfe42d4162a47e65272a3a4cc4
    73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Information and Computing Sciences
    75 rdf:type schema:DefinedTerm
    76 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    77 schema:name Computation Theory and Mathematics
    78 rdf:type schema:DefinedTerm
    79 sg:person.010013323122.87 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    80 schema:familyName Caminiti
    81 schema:givenName Saverio
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87
    83 rdf:type schema:Person
    84 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    85 schema:familyName Petreschi
    86 schema:givenName Rossella
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    88 rdf:type schema:Person
    89 sg:person.014240412541.72 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    90 schema:familyName Finocchi
    91 schema:givenName Irene
    92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72
    93 rdf:type schema:Person
    94 sg:pub.10.1007/11780823_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032547776
    95 https://doi.org/10.1007/11780823_12
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/3-540-44612-5_53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032559164
    98 https://doi.org/10.1007/3-540-44612-5_53
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/3-540-46784-x_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003259743
    101 https://doi.org/10.1007/3-540-46784-x_5
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/0022-247x(67)90082-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040665844
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/j.tcs.2007.03.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053662883
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1109/tit.1966.1053860 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061646188
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1137/s0097539700370539 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879236
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1137/s0097539703433912 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879473
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1137/s0097539703437211 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879498
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1137/s0895480103433409 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882719
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1145/564870.564914 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009882975
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1145/62212.62244 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022515096
    120 rdf:type schema:CreativeWork
    121 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    122 schema:name Computer Science Department, Sapienza University of Rome, Via Salaria, 113, 00198, Rome, Italy
    123 rdf:type schema:Organization
     




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


    ...