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

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 N8afe70ea5e48469ea33696255b4cb84e
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 N597f0477b9f045d1a5f3c784206a58bd
20 schema:genre chapter
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N4367ca80e4454ac6805e5307a5e1344b
24 schema:name Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors
25 schema:pagination 234-245
26 schema:productId N15608116f923479e969554a1457ba8a9
27 Nb559814ecf8b47cfad6e49e2ba5a3840
28 Nfc39408092f24ace80bbcc2d419a5bfd
29 schema:publisher N95fba86dd1bb4012b442b8c2659fa267
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 N13534216558840cf9f7462086e14f7a6
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 N13534216558840cf9f7462086e14f7a6 schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N15608116f923479e969554a1457ba8a9 schema:name doi
42 schema:value 10.1007/978-3-540-87744-8_20
43 rdf:type schema:PropertyValue
44 N4367ca80e4454ac6805e5307a5e1344b schema:isbn 978-3-540-87743-1
45 978-3-540-87744-8
46 schema:name Algorithms - ESA 2008
47 rdf:type schema:Book
48 N47d192093b0b48169c3dc405dbabdc93 schema:familyName Halperin
49 schema:givenName Dan
50 rdf:type schema:Person
51 N597f0477b9f045d1a5f3c784206a58bd rdf:first N47d192093b0b48169c3dc405dbabdc93
52 rdf:rest N95ff1e92d0d747648894f619cc46baf4
53 N72cedf1aeb5641a99684398e2692cff2 rdf:first sg:person.011402427702.78
54 rdf:rest rdf:nil
55 N891e4e2167cc41bb990a13295d6345ee schema:familyName Mehlhorn
56 schema:givenName Kurt
57 rdf:type schema:Person
58 N8afe70ea5e48469ea33696255b4cb84e rdf:first sg:person.010013323122.87
59 rdf:rest N8d21cbaf6e824ef3ad233202604961d8
60 N8d21cbaf6e824ef3ad233202604961d8 rdf:first sg:person.014240412541.72
61 rdf:rest N72cedf1aeb5641a99684398e2692cff2
62 N95fba86dd1bb4012b442b8c2659fa267 schema:location Berlin, Heidelberg
63 schema:name Springer Berlin Heidelberg
64 rdf:type schema:Organisation
65 N95ff1e92d0d747648894f619cc46baf4 rdf:first N891e4e2167cc41bb990a13295d6345ee
66 rdf:rest rdf:nil
67 Nb559814ecf8b47cfad6e49e2ba5a3840 schema:name readcube_id
68 schema:value a88f3b3e4ba1ddebed256c83bb876716da4bfecefdd4a6b2f160d012b13e2492
69 rdf:type schema:PropertyValue
70 Nfc39408092f24ace80bbcc2d419a5bfd schema:name dimensions_id
71 schema:value pub.1035385068
72 rdf:type schema:PropertyValue
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)


...