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 Nb132a87d8dc5472e8cbcb329e0936fe3
    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 Ne0231665ee944050a423cb37cbea1628
    26 schema:genre chapter
    27 schema:inLanguage en
    28 schema:isAccessibleForFree true
    29 schema:isPartOf N9716bc229dfa4de1ae9f7ed014c884c4
    30 schema:name Parallel Algorithms for Encoding and Decoding Blob Code
    31 schema:pagination 167-178
    32 schema:productId N2dafb201547f408191dd36556441e1dd
    33 N6bd395d6f6ca434995e0bf7ed1713066
    34 N70d86743880a4dc58b88c41ce68c6f75
    35 schema:publisher N0a28f574f8d24b4e89b1d53323382be4
    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 Nccdf125edb7a4548a509c0bd94abf7a5
    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 N0a28f574f8d24b4e89b1d53323382be4 schema:location Berlin, Heidelberg
    46 schema:name Springer Berlin Heidelberg
    47 rdf:type schema:Organisation
    48 N2dafb201547f408191dd36556441e1dd schema:name readcube_id
    49 schema:value d7e119981b5fc08e50fdaefa90060c8b0c216ec73ae0681a112035912e90c9bb
    50 rdf:type schema:PropertyValue
    51 N4281148fefca401aa5417e89bf36207f schema:familyName Fujita
    52 schema:givenName Satoshi
    53 rdf:type schema:Person
    54 N451e300b23e84897919d0d9862dc788f rdf:first N4281148fefca401aa5417e89bf36207f
    55 rdf:rest rdf:nil
    56 N6bd395d6f6ca434995e0bf7ed1713066 schema:name dimensions_id
    57 schema:value pub.1045320419
    58 rdf:type schema:PropertyValue
    59 N70d86743880a4dc58b88c41ce68c6f75 schema:name doi
    60 schema:value 10.1007/978-3-642-11440-3_16
    61 rdf:type schema:PropertyValue
    62 N9716bc229dfa4de1ae9f7ed014c884c4 schema:isbn 978-3-642-11439-7
    63 978-3-642-11440-3
    64 schema:name WALCOM: Algorithms and Computation
    65 rdf:type schema:Book
    66 Nb132a87d8dc5472e8cbcb329e0936fe3 rdf:first sg:person.010013323122.87
    67 rdf:rest Ne10859e7edf2494da78fc3cd00c93548
    68 Ncc884f7d3fa0452282752f813d29bfc1 schema:familyName Rahman
    69 schema:givenName Md. Saidur
    70 rdf:type schema:Person
    71 Nccdf125edb7a4548a509c0bd94abf7a5 schema:name Springer Nature - SN SciGraph project
    72 rdf:type schema:Organization
    73 Ne0231665ee944050a423cb37cbea1628 rdf:first Ncc884f7d3fa0452282752f813d29bfc1
    74 rdf:rest N451e300b23e84897919d0d9862dc788f
    75 Ne10859e7edf2494da78fc3cd00c93548 rdf:first sg:person.011402427702.78
    76 rdf:rest rdf:nil
    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)


    ...