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

References to SciGraph publications

  • 2005. Distributed Maintenance of a Spanning Tree Using Labeled Tree Encoding in EURO-PAR 2005 PARALLEL PROCESSING
  • 2005. String Coding of Trees with Locality and Heritability in COMPUTING AND COMBINATORICS
  • 2009. Parallel Algorithms for Dandelion-Like Codes in COMPUTATIONAL SCIENCE – ICCS 2009
  • 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 N09db619d464541d8836ee1d725386806
    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 Nfc14525212d7418a89325e4f1656b46f
    26 schema:genre chapter
    27 schema:inLanguage en
    28 schema:isAccessibleForFree true
    29 schema:isPartOf N4b099df7e1464614accfcaf65a777cf1
    30 schema:name Parallel Algorithms for Encoding and Decoding Blob Code
    31 schema:pagination 167-178
    32 schema:productId N54bc42a637734017b0b70109999e5b76
    33 Nf27a142250c64a1e8844d6742e0a317d
    34 Nfd850bf9a878420c8db60d9e9a27f591
    35 schema:publisher Nfd91207b7ceb4ff4816e48ee820c357f
    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 N41ec86bc13724c108d476182c20b822f
    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 N09db619d464541d8836ee1d725386806 rdf:first sg:person.010013323122.87
    46 rdf:rest Nc9de0939f03d45308b56a04020e48f32
    47 N41ec86bc13724c108d476182c20b822f schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 N4b099df7e1464614accfcaf65a777cf1 schema:isbn 978-3-642-11439-7
    50 978-3-642-11440-3
    51 schema:name WALCOM: Algorithms and Computation
    52 rdf:type schema:Book
    53 N5419cb397edd430d956dbbf4683ae48e rdf:first Nce9a6955d80742c7826e29fcedaf5325
    54 rdf:rest rdf:nil
    55 N54bc42a637734017b0b70109999e5b76 schema:name doi
    56 schema:value 10.1007/978-3-642-11440-3_16
    57 rdf:type schema:PropertyValue
    58 Nc9de0939f03d45308b56a04020e48f32 rdf:first sg:person.011402427702.78
    59 rdf:rest rdf:nil
    60 Nce9a6955d80742c7826e29fcedaf5325 schema:familyName Fujita
    61 schema:givenName Satoshi
    62 rdf:type schema:Person
    63 Nd1caf28d2c2e4e17a5416bd9f2599199 schema:familyName Rahman
    64 schema:givenName Md. Saidur
    65 rdf:type schema:Person
    66 Nf27a142250c64a1e8844d6742e0a317d schema:name dimensions_id
    67 schema:value pub.1045320419
    68 rdf:type schema:PropertyValue
    69 Nfc14525212d7418a89325e4f1656b46f rdf:first Nd1caf28d2c2e4e17a5416bd9f2599199
    70 rdf:rest N5419cb397edd430d956dbbf4683ae48e
    71 Nfd850bf9a878420c8db60d9e9a27f591 schema:name readcube_id
    72 schema:value d7e119981b5fc08e50fdaefa90060c8b0c216ec73ae0681a112035912e90c9bb
    73 rdf:type schema:PropertyValue
    74 Nfd91207b7ceb4ff4816e48ee820c357f schema:location Berlin, Heidelberg
    75 schema:name Springer Berlin Heidelberg
    76 rdf:type schema:Organisation
    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)


    ...