Parallel Algorithms for Encoding and Decoding Blob Code View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Saverio Caminiti , Rossella Petreschi

ABSTRACT

A bijective code is a method for associating labeled n-trees to (n − 2)-strings of node labels in such a way that different trees yield different strings and vice versa. For all known bijective codes, optimal sequential encoding and decoding algorithms are presented in literature, while parallel algorithms are investigated only for some of these codes. In this paper we focus our attention on the Blob code: a code particularly considered in the field of Genetic Algorithms. To the best of our knowledge, here we present the first parallel encoding and decoding algorithms for this code. The encoding algorithm implementation is optimal on an EREW PRAM, while the decoding algorithm requires O(logn) time and O(n) processors on CREW PRAM. More... »

PAGES

167-178

Book

TITLE

WALCOM: Algorithms and Computation

ISBN

978-3-642-11439-7
978-3-642-11440-3

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-11440-3_16

DOI

http://dx.doi.org/10.1007/978-3-642-11440-3_16

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "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": "https://doi.org/10.1016/s0166-218x(99)00221-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006258311"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-01970-8_60", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014153232", 
          "https://doi.org/10.1007/978-3-642-01970-8_60"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-01970-8_60", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014153232", 
          "https://doi.org/10.1007/978-3-642-01970-8_60"
        ], 
        "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": "https://doi.org/10.1201/9781420011296.ch5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023825386"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/1276958.1277207", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1025340769"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/322217.322232", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026733562"
        ], 
        "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": "https://doi.org/10.1016/0095-8956(78)90038-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046502233"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/321812.321815", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046664876"
        ], 
        "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.1145/1068009.1068108", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048953459"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1073/pnas.87.24.9635", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052022098"
        ], 
        "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": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "A bijective code is a method for associating labeled n-trees to (n \u2212 2)-strings of node labels in such a way that different trees yield different strings and vice versa. For all known bijective codes, optimal sequential encoding and decoding algorithms are presented in literature, while parallel algorithms are investigated only for some of these codes. In this paper we focus our attention on the Blob code: a code particularly considered in the field of Genetic Algorithms. To the best of our knowledge, here we present the first parallel encoding and decoding algorithms for this code. The encoding algorithm implementation is optimal on an EREW PRAM, while the decoding algorithm requires O(logn) time and O(n) processors on CREW PRAM.", 
    "editor": [
      {
        "familyName": "Rahman", 
        "givenName": "Md. Saidur", 
        "type": "Person"
      }, 
      {
        "familyName": "Fujita", 
        "givenName": "Satoshi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-11440-3_16", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-11439-7", 
        "978-3-642-11440-3"
      ], 
      "name": "WALCOM: Algorithms and Computation", 
      "type": "Book"
    }, 
    "name": "Parallel Algorithms for Encoding and Decoding Blob Code", 
    "pagination": "167-178", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045320419"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-11440-3_16"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d7e119981b5fc08e50fdaefa90060c8b0c216ec73ae0681a112035912e90c9bb"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-11440-3_16", 
      "https://app.dimensions.ai/details/publication/pub.1045320419"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:32", 
    "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/0000000356_0000000356/records_57900_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-11440-3_16"
  }
]
 

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-11440-3_16'

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-11440-3_16'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-11440-3_16'

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-11440-3_16'


 

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

134 TRIPLES      23 PREDICATES      45 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-11440-3_16 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N23fb1f70b2654071b38efb421952dde2
4 schema:citation sg:pub.10.1007/11533719_27
5 sg:pub.10.1007/11549468_68
6 sg:pub.10.1007/978-3-642-01970-8_60
7 https://doi.org/10.1016/0012-365x(91)90138-r
8 https://doi.org/10.1016/0095-8956(78)90038-2
9 https://doi.org/10.1016/0097-3165(86)90004-x
10 https://doi.org/10.1016/j.tcs.2007.03.009
11 https://doi.org/10.1016/s0166-218x(99)00221-8
12 https://doi.org/10.1017/s030500410002853x
13 https://doi.org/10.1073/pnas.87.24.9635
14 https://doi.org/10.1109/cec.2006.1688567
15 https://doi.org/10.1109/vtest.1996.510854
16 https://doi.org/10.1145/1068009.1068108
17 https://doi.org/10.1145/1248377.1248427
18 https://doi.org/10.1145/1276958.1277207
19 https://doi.org/10.1145/321812.321815
20 https://doi.org/10.1145/322217.322232
21 https://doi.org/10.1201/9781420011296.ch5
22 schema:datePublished 2010
23 schema:datePublishedReg 2010-01-01
24 schema:description A bijective code is a method for associating labeled n-trees to (n − 2)-strings of node labels in such a way that different trees yield different strings and vice versa. For all known bijective codes, optimal sequential encoding and decoding algorithms are presented in literature, while parallel algorithms are investigated only for some of these codes. In this paper we focus our attention on the Blob code: a code particularly considered in the field of Genetic Algorithms. To the best of our knowledge, here we present the first parallel encoding and decoding algorithms for this code. The encoding algorithm implementation is optimal on an EREW PRAM, while the decoding algorithm requires O(logn) time and O(n) processors on CREW PRAM.
25 schema:editor N7269f8c9303b4730896f82125cdce52d
26 schema:genre chapter
27 schema:inLanguage en
28 schema:isAccessibleForFree true
29 schema:isPartOf N6e1cda9eeed94c2c8883dfb6d4d1b7eb
30 schema:name Parallel Algorithms for Encoding and Decoding Blob Code
31 schema:pagination 167-178
32 schema:productId Nd7a36329fe914684bbf226235b1c403b
33 Ne102529f8a474446bd1f965176454f67
34 Nf2953dd811674cb188e493bbe76712de
35 schema:publisher N8ee30c953ef742828cf5453ed8371aec
36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045320419
37 https://doi.org/10.1007/978-3-642-11440-3_16
38 schema:sdDatePublished 2019-04-16T07:32
39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
40 schema:sdPublisher Na2ce1416e1c34a9686add53db3d34945
41 schema:url https://link.springer.com/10.1007%2F978-3-642-11440-3_16
42 sgo:license sg:explorer/license/
43 sgo:sdDataset chapters
44 rdf:type schema:Chapter
45 N1953049890d9410b8ee03cba5f5084b5 rdf:first sg:person.011402427702.78
46 rdf:rest rdf:nil
47 N23fb1f70b2654071b38efb421952dde2 rdf:first sg:person.010013323122.87
48 rdf:rest N1953049890d9410b8ee03cba5f5084b5
49 N643fa98da6054362ba433351be8915e7 schema:familyName Fujita
50 schema:givenName Satoshi
51 rdf:type schema:Person
52 N6e1cda9eeed94c2c8883dfb6d4d1b7eb schema:isbn 978-3-642-11439-7
53 978-3-642-11440-3
54 schema:name WALCOM: Algorithms and Computation
55 rdf:type schema:Book
56 N7269f8c9303b4730896f82125cdce52d rdf:first Nd6a143be0a6a417a925f5a492195543f
57 rdf:rest N744d63ec33c3437782adc53c14d6c69c
58 N744d63ec33c3437782adc53c14d6c69c rdf:first N643fa98da6054362ba433351be8915e7
59 rdf:rest rdf:nil
60 N8ee30c953ef742828cf5453ed8371aec schema:location Berlin, Heidelberg
61 schema:name Springer Berlin Heidelberg
62 rdf:type schema:Organisation
63 Na2ce1416e1c34a9686add53db3d34945 schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 Nd6a143be0a6a417a925f5a492195543f schema:familyName Rahman
66 schema:givenName Md. Saidur
67 rdf:type schema:Person
68 Nd7a36329fe914684bbf226235b1c403b schema:name readcube_id
69 schema:value d7e119981b5fc08e50fdaefa90060c8b0c216ec73ae0681a112035912e90c9bb
70 rdf:type schema:PropertyValue
71 Ne102529f8a474446bd1f965176454f67 schema:name doi
72 schema:value 10.1007/978-3-642-11440-3_16
73 rdf:type schema:PropertyValue
74 Nf2953dd811674cb188e493bbe76712de schema:name dimensions_id
75 schema:value pub.1045320419
76 rdf:type schema:PropertyValue
77 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
78 schema:name Mathematical Sciences
79 rdf:type schema:DefinedTerm
80 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
81 schema:name Numerical and Computational Mathematics
82 rdf:type schema:DefinedTerm
83 sg:person.010013323122.87 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
84 schema:familyName Caminiti
85 schema:givenName Saverio
86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87
87 rdf:type schema:Person
88 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
89 schema:familyName Petreschi
90 schema:givenName Rossella
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
92 rdf:type schema:Person
93 sg:pub.10.1007/11533719_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047625411
94 https://doi.org/10.1007/11533719_27
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/11549468_68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014293617
97 https://doi.org/10.1007/11549468_68
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/978-3-642-01970-8_60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014153232
100 https://doi.org/10.1007/978-3-642-01970-8_60
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/0012-365x(91)90138-r schema:sameAs https://app.dimensions.ai/details/publication/pub.1003371094
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/0095-8956(78)90038-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046502233
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/0097-3165(86)90004-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1038613771
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/j.tcs.2007.03.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053662883
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/s0166-218x(99)00221-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006258311
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1017/s030500410002853x schema:sameAs https://app.dimensions.ai/details/publication/pub.1054084145
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1073/pnas.87.24.9635 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052022098
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1109/cec.2006.1688567 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094400901
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1109/vtest.1996.510854 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094169292
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1145/1068009.1068108 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048953459
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1145/1248377.1248427 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045405950
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/1276958.1277207 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025340769
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1145/321812.321815 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046664876
127 rdf:type schema:CreativeWork
128 https://doi.org/10.1145/322217.322232 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026733562
129 rdf:type schema:CreativeWork
130 https://doi.org/10.1201/9781420011296.ch5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023825386
131 rdf:type schema:CreativeWork
132 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
133 schema:name Computer Science Department, Sapienza University of Rome, Via Salaria, 113, I00198, Rome, Italy
134 rdf:type schema:Organization
 




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


...