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 N66e0d2c023bd4400a8d6da37f147d84c
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 N1dd73a7d6cf443c69fb5406ca06c452e
18 schema:genre chapter
19 schema:inLanguage en
20 schema:isAccessibleForFree true
21 schema:isPartOf N9aea5963a14249bfb13b2661d6863efc
22 schema:name Parallel Algorithms for Dandelion-Like Codes
23 schema:pagination 611-620
24 schema:productId N4f44973b437b4967a419011931c850dd
25 N5c4a1c0d34fa4008a780fd4bb9038675
26 Nbd82ba3f1ff54b5b86c53931061c1362
27 schema:publisher Nd1a0f3653d154501866dbf917fdc65ab
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 N6967f036cdea44ad9343488e0c3d5b7b
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 N19a37ec58cb0411f86f06a447f7c1c48 schema:familyName van Albada
38 schema:givenName Geert Dick
39 rdf:type schema:Person
40 N1dd73a7d6cf443c69fb5406ca06c452e rdf:first Ncf8038ddc9ff4fc6b1f2457241bd4415
41 rdf:rest N30d46c06cf2643fa88c98b69df64c5f9
42 N30d46c06cf2643fa88c98b69df64c5f9 rdf:first Nc75ac07faee14d9da33b8141dc08af41
43 rdf:rest Nf52a9edf1dab4114b17deb8c7cc1dbef
44 N357bd06a6f804f4b9de7bb9fa1991545 rdf:first N8183d9c215484795a9decf5d0b2bac1f
45 rdf:rest N9bbeb40a7d274fa3a2d2fe91b4431962
46 N4f44973b437b4967a419011931c850dd schema:name readcube_id
47 schema:value 436cff909fc5283caaba1ff7ad790a378270753b8c0fd3b6b01dd73be7043c84
48 rdf:type schema:PropertyValue
49 N5c4a1c0d34fa4008a780fd4bb9038675 schema:name dimensions_id
50 schema:value pub.1014153232
51 rdf:type schema:PropertyValue
52 N66e0d2c023bd4400a8d6da37f147d84c rdf:first sg:person.010013323122.87
53 rdf:rest N83fbf454ec7e483e98116a42fe968afe
54 N6967f036cdea44ad9343488e0c3d5b7b schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 N8183d9c215484795a9decf5d0b2bac1f schema:familyName Dongarra
57 schema:givenName Jack
58 rdf:type schema:Person
59 N83fbf454ec7e483e98116a42fe968afe rdf:first sg:person.011402427702.78
60 rdf:rest rdf:nil
61 N9661eb9e7d7449aaa07adc6016f9d9ec schema:familyName Sloot
62 schema:givenName Peter M. A.
63 rdf:type schema:Person
64 N9aea5963a14249bfb13b2661d6863efc schema:isbn 978-3-642-01969-2
65 978-3-642-01970-8
66 schema:name Computational Science – ICCS 2009
67 rdf:type schema:Book
68 N9bbeb40a7d274fa3a2d2fe91b4431962 rdf:first N9661eb9e7d7449aaa07adc6016f9d9ec
69 rdf:rest rdf:nil
70 Nb48b4012085b45e0b95c449ae3f223a2 rdf:first N19a37ec58cb0411f86f06a447f7c1c48
71 rdf:rest N357bd06a6f804f4b9de7bb9fa1991545
72 Nb79f97e115b64e85b68bc941511b008e schema:familyName Seidel
73 schema:givenName Edward
74 rdf:type schema:Person
75 Nbd82ba3f1ff54b5b86c53931061c1362 schema:name doi
76 schema:value 10.1007/978-3-642-01970-8_60
77 rdf:type schema:PropertyValue
78 Nc75ac07faee14d9da33b8141dc08af41 schema:familyName Nabrzyski
79 schema:givenName Jarosław
80 rdf:type schema:Person
81 Ncf8038ddc9ff4fc6b1f2457241bd4415 schema:familyName Allen
82 schema:givenName Gabrielle
83 rdf:type schema:Person
84 Nd1a0f3653d154501866dbf917fdc65ab schema:location Berlin, Heidelberg
85 schema:name Springer Berlin Heidelberg
86 rdf:type schema:Organisation
87 Nf52a9edf1dab4114b17deb8c7cc1dbef rdf:first Nb79f97e115b64e85b68bc941511b008e
88 rdf:rest Nb48b4012085b45e0b95c449ae3f223a2
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)


...