Parallel Algorithms for Dandelion-Like Codes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Saverio Caminiti , Rossella Petreschi

ABSTRACT

We consider the class of Dandelion-like codes, i.e., a class of bijective codes for coding labeled trees by means of strings of node labels. In the literature it is possible to find optimal sequential algorithms for codes belonging to this class, but, for the best of our knowledge, no parallel algorithm is reported. In this paper we present the first encoding and decoding parallel algorithms for Dandelion-like codes. Namely, we design a unique encoding algorithm and a unique decoding algorithm that, properly parametrized, can be used for all Dandelion-like codes. These algorithms are optimal in the sequential setting. The encoding algorithm implementation on an EREW PRAM is optimal, while the efficient implementation of the decoding algorithm requires concurrent reading. More... »

PAGES

611-620

References to SciGraph publications

Book

TITLE

Computational Science – ICCS 2009

ISBN

978-3-642-01969-2
978-3-642-01970-8

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-01970-8_60

DOI

http://dx.doi.org/10.1007/978-3-642-01970-8_60

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "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, I00198, 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, I00198, 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": "https://doi.org/10.1016/0012-365x(91)90138-r", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1003371094"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11549468_68", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014293617", 
          "https://doi.org/10.1007/11549468_68"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11549468_68", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014293617", 
          "https://doi.org/10.1007/11549468_68"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s002249910006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037393494", 
          "https://doi.org/10.1007/s002249910006"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0097-3165(86)90004-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038613771"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1248377.1248427", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045405950"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11533719_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047625411", 
          "https://doi.org/10.1007/11533719_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11533719_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047625411", 
          "https://doi.org/10.1007/11533719_27"
        ], 
        "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.1017/s030500410002853x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1054084145"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/vtest.1996.510854", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094169292"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/cec.2006.1688567", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094400901"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We consider the class of Dandelion-like codes, i.e., a class of bijective codes for coding labeled trees by means of strings of node labels. In the literature it is possible to find optimal sequential algorithms for codes belonging to this class, but, for the best of our knowledge, no parallel algorithm is reported. In this paper we present the first encoding and decoding parallel algorithms for Dandelion-like codes. Namely, we design a unique encoding algorithm and a unique decoding algorithm that, properly parametrized, can be used for all Dandelion-like codes. These algorithms are optimal in the sequential setting. The encoding algorithm implementation on an EREW PRAM is optimal, while the efficient implementation of the decoding algorithm requires concurrent reading.", 
    "editor": [
      {
        "familyName": "Allen", 
        "givenName": "Gabrielle", 
        "type": "Person"
      }, 
      {
        "familyName": "Nabrzyski", 
        "givenName": "Jaros\u0142aw", 
        "type": "Person"
      }, 
      {
        "familyName": "Seidel", 
        "givenName": "Edward", 
        "type": "Person"
      }, 
      {
        "familyName": "van Albada", 
        "givenName": "Geert Dick", 
        "type": "Person"
      }, 
      {
        "familyName": "Dongarra", 
        "givenName": "Jack", 
        "type": "Person"
      }, 
      {
        "familyName": "Sloot", 
        "givenName": "Peter M. A.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-01970-8_60", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-01969-2", 
        "978-3-642-01970-8"
      ], 
      "name": "Computational Science \u2013 ICCS 2009", 
      "type": "Book"
    }, 
    "name": "Parallel Algorithms for Dandelion-Like Codes", 
    "pagination": "611-620", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014153232"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-01970-8_60"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "436cff909fc5283caaba1ff7ad790a378270753b8c0fd3b6b01dd73be7043c84"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-01970-8_60", 
      "https://app.dimensions.ai/details/publication/pub.1014153232"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:12", 
    "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/0000000353_0000000353/records_45354_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-01970-8_60"
  }
]
 

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-642-01970-8_60'

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-642-01970-8_60'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-01970-8_60'

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-642-01970-8_60'


 

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

130 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-01970-8_60 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nb0e27e02aaae44879320e582adeb52f8
4 schema:citation sg:pub.10.1007/11533719_27
5 sg:pub.10.1007/11549468_68
6 sg:pub.10.1007/s002249910006
7 https://doi.org/10.1016/0012-365x(91)90138-r
8 https://doi.org/10.1016/0097-3165(86)90004-x
9 https://doi.org/10.1016/j.tcs.2007.03.009
10 https://doi.org/10.1017/s030500410002853x
11 https://doi.org/10.1109/cec.2006.1688567
12 https://doi.org/10.1109/vtest.1996.510854
13 https://doi.org/10.1145/1248377.1248427
14 schema:datePublished 2009
15 schema:datePublishedReg 2009-01-01
16 schema:description We consider the class of Dandelion-like codes, i.e., a class of bijective codes for coding labeled trees by means of strings of node labels. In the literature it is possible to find optimal sequential algorithms for codes belonging to this class, but, for the best of our knowledge, no parallel algorithm is reported. In this paper we present the first encoding and decoding parallel algorithms for Dandelion-like codes. Namely, we design a unique encoding algorithm and a unique decoding algorithm that, properly parametrized, can be used for all Dandelion-like codes. These algorithms are optimal in the sequential setting. The encoding algorithm implementation on an EREW PRAM is optimal, while the efficient implementation of the decoding algorithm requires concurrent reading.
17 schema:editor N434ddb37642445d0895e72d158ca03f8
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf Nb8a028f3353942918c712238ec5f0a8e
22 schema:name Parallel Algorithms for Dandelion-Like Codes
23 schema:pagination 611-620
24 schema:productId N1f5db4eb665442c0bc51af69418d190f
25 N92f1d681a5334b679fdd365d9319e202
26 Na6bc4650ce84466f80addda6417c825e
27 schema:publisher N840feb498adc46fc9c4492ae40024ee4
28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014153232
29 https://doi.org/10.1007/978-3-642-01970-8_60
30 schema:sdDatePublished 2019-04-16T07:12
31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
32 schema:sdPublisher N8744affe57aa49a5aa07a19b06c7ebd6
33 schema:url https://link.springer.com/10.1007%2F978-3-642-01970-8_60
34 sgo:license sg:explorer/license/
35 sgo:sdDataset chapters
36 rdf:type schema:Chapter
37 N1f5db4eb665442c0bc51af69418d190f schema:name dimensions_id
38 schema:value pub.1014153232
39 rdf:type schema:PropertyValue
40 N3c7f17f989214ca9adb95df3253525c2 schema:familyName van Albada
41 schema:givenName Geert Dick
42 rdf:type schema:Person
43 N434ddb37642445d0895e72d158ca03f8 rdf:first N987971759cb247f789985886575bddf0
44 rdf:rest N7aad7c4294a247638194901ecef9429f
45 N4d8ce59815e94dc0b86994554b0b3ee5 rdf:first N3c7f17f989214ca9adb95df3253525c2
46 rdf:rest Nb5b1634d05734de592a934e6af29dad9
47 N4f3e241896a14077b99d5fae4654454d schema:familyName Sloot
48 schema:givenName Peter M. A.
49 rdf:type schema:Person
50 N6a49a1ee496c4f6d9eab4d558b33e8a2 rdf:first N4f3e241896a14077b99d5fae4654454d
51 rdf:rest rdf:nil
52 N7aad7c4294a247638194901ecef9429f rdf:first Nce03b2ae4ba544f0a138bb9e50933ee8
53 rdf:rest Ncf890b0e17ea4511a5276a94c4cb862a
54 N840feb498adc46fc9c4492ae40024ee4 schema:location Berlin, Heidelberg
55 schema:name Springer Berlin Heidelberg
56 rdf:type schema:Organisation
57 N8744affe57aa49a5aa07a19b06c7ebd6 schema:name Springer Nature - SN SciGraph project
58 rdf:type schema:Organization
59 N8957004af95c434598581acb1394a564 rdf:first sg:person.011402427702.78
60 rdf:rest rdf:nil
61 N92f1d681a5334b679fdd365d9319e202 schema:name readcube_id
62 schema:value 436cff909fc5283caaba1ff7ad790a378270753b8c0fd3b6b01dd73be7043c84
63 rdf:type schema:PropertyValue
64 N987971759cb247f789985886575bddf0 schema:familyName Allen
65 schema:givenName Gabrielle
66 rdf:type schema:Person
67 N9ce4e72f57cd49e482a5560fe0453653 schema:familyName Seidel
68 schema:givenName Edward
69 rdf:type schema:Person
70 Na6bc4650ce84466f80addda6417c825e schema:name doi
71 schema:value 10.1007/978-3-642-01970-8_60
72 rdf:type schema:PropertyValue
73 Nb0e27e02aaae44879320e582adeb52f8 rdf:first sg:person.010013323122.87
74 rdf:rest N8957004af95c434598581acb1394a564
75 Nb5b1634d05734de592a934e6af29dad9 rdf:first Nb6b291a94b01405eaf68c839f1e33928
76 rdf:rest N6a49a1ee496c4f6d9eab4d558b33e8a2
77 Nb6b291a94b01405eaf68c839f1e33928 schema:familyName Dongarra
78 schema:givenName Jack
79 rdf:type schema:Person
80 Nb8a028f3353942918c712238ec5f0a8e schema:isbn 978-3-642-01969-2
81 978-3-642-01970-8
82 schema:name Computational Science – ICCS 2009
83 rdf:type schema:Book
84 Nce03b2ae4ba544f0a138bb9e50933ee8 schema:familyName Nabrzyski
85 schema:givenName Jarosław
86 rdf:type schema:Person
87 Ncf890b0e17ea4511a5276a94c4cb862a rdf:first N9ce4e72f57cd49e482a5560fe0453653
88 rdf:rest N4d8ce59815e94dc0b86994554b0b3ee5
89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
90 schema:name Information and Computing Sciences
91 rdf:type schema:DefinedTerm
92 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
93 schema:name Data Format
94 rdf:type schema:DefinedTerm
95 sg:person.010013323122.87 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
96 schema:familyName Caminiti
97 schema:givenName Saverio
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87
99 rdf:type schema:Person
100 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
101 schema:familyName Petreschi
102 schema:givenName Rossella
103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
104 rdf:type schema:Person
105 sg:pub.10.1007/11533719_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047625411
106 https://doi.org/10.1007/11533719_27
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/11549468_68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014293617
109 https://doi.org/10.1007/11549468_68
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/s002249910006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037393494
112 https://doi.org/10.1007/s002249910006
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1016/0012-365x(91)90138-r schema:sameAs https://app.dimensions.ai/details/publication/pub.1003371094
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1016/0097-3165(86)90004-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1038613771
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1016/j.tcs.2007.03.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053662883
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1017/s030500410002853x schema:sameAs https://app.dimensions.ai/details/publication/pub.1054084145
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1109/cec.2006.1688567 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094400901
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1109/vtest.1996.510854 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094169292
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/1248377.1248427 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045405950
127 rdf:type schema:CreativeWork
128 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
129 schema:name Computer Science Department, Sapienza University of Rome, Via Salaria, 113, I00198, Rome, Italy
130 rdf:type schema:Organization
 




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


...