Parallel heap: An optimal parallel priority queue View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1992-03

AUTHORS

Narsingh Deo, Sushil Prasad

ABSTRACT

We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the parallel heap allows deletions of θ(p) highest priority items and insertions of θ(p) new items, each in O(log n) time, where n is the size of the parallel heap. Furthermore, it can efficiently utilize processors in the range 1 through n. More... »

PAGES

87-98

References to SciGraph publications

  • 1983. Parallel dictionaries on 2–3 trees in AUTOMATA, LANGUAGES AND PROGRAMMING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/bf00128644

    DOI

    http://dx.doi.org/10.1007/bf00128644

    DIMENSIONS

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


    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/0803", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computer Software", 
            "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": "University of Central Florida", 
              "id": "https://www.grid.ac/institutes/grid.170430.1", 
              "name": [
                "Computer Science Department, University of Central Florida, 32816, Orlando, FL, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Deo", 
            "givenName": "Narsingh", 
            "id": "sg:person.010274011142.47", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Georgia State University", 
              "id": "https://www.grid.ac/institutes/grid.256304.6", 
              "name": [
                "Mathematics and Computer Science Department, Georgia State University, 30303, Atlanta, GA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Prasad", 
            "givenName": "Sushil", 
            "id": "sg:person.012217451543.37", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012217451543.37"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1145/63238.63249", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005973242"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/b978-0-444-88071-0.50022-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007005196"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(89)90138-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014637820"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2514.2515", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015803283"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0036940", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028714319", 
              "https://doi.org/10.1007/bfb0036940"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/84537.84545", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031796676"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(84)90128-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035509960"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/12.9744", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061089433"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/32.29490", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061153847"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tc.1980.1675680", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061532487"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tse.1984.5010306", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061787736"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0215068", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841930"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0217049", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842068"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0218014", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062842113"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/ipps.1992.223004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086290914"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/wsc.1991.185670", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086305019"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1992-03", 
        "datePublishedReg": "1992-03-01", 
        "description": "We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the parallel heap allows deletions of \u03b8(p) highest priority items and insertions of \u03b8(p) new items, each in O(log n) time, where n is the size of the parallel heap. Furthermore, it can efficiently utilize processors in the range 1 through n.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/bf00128644", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1133522", 
            "issn": [
              "0920-8542", 
              "1573-0484"
            ], 
            "name": "The Journal of Supercomputing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "6"
          }
        ], 
        "name": "Parallel heap: An optimal parallel priority queue", 
        "pagination": "87-98", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "226713107096bdf855ccfee66a8a731b9987a1a9c1dd24bcd24d77099c53c7a3"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/bf00128644"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1007222595"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/bf00128644", 
          "https://app.dimensions.ai/details/publication/pub.1007222595"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T13:56", 
        "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/0000000371_0000000371/records_130817_00000000.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/BF00128644"
      }
    ]
     

    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/bf00128644'

    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/bf00128644'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf00128644'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf00128644'


     

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

    120 TRIPLES      21 PREDICATES      43 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/bf00128644 schema:about anzsrc-for:08
    2 anzsrc-for:0803
    3 schema:author Neba8a0c5cfe742cda0ab0814c1280377
    4 schema:citation sg:pub.10.1007/bfb0036940
    5 https://doi.org/10.1016/0020-0190(84)90128-5
    6 https://doi.org/10.1016/0020-0190(89)90138-5
    7 https://doi.org/10.1016/b978-0-444-88071-0.50022-9
    8 https://doi.org/10.1109/12.9744
    9 https://doi.org/10.1109/32.29490
    10 https://doi.org/10.1109/ipps.1992.223004
    11 https://doi.org/10.1109/tc.1980.1675680
    12 https://doi.org/10.1109/tse.1984.5010306
    13 https://doi.org/10.1109/wsc.1991.185670
    14 https://doi.org/10.1137/0215068
    15 https://doi.org/10.1137/0217049
    16 https://doi.org/10.1137/0218014
    17 https://doi.org/10.1145/2514.2515
    18 https://doi.org/10.1145/63238.63249
    19 https://doi.org/10.1145/84537.84545
    20 schema:datePublished 1992-03
    21 schema:datePublishedReg 1992-03-01
    22 schema:description We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the parallel heap allows deletions of θ(p) highest priority items and insertions of θ(p) new items, each in O(log n) time, where n is the size of the parallel heap. Furthermore, it can efficiently utilize processors in the range 1 through n.
    23 schema:genre research_article
    24 schema:inLanguage en
    25 schema:isAccessibleForFree false
    26 schema:isPartOf N2640a5a13e1f40f1a49fb26e64c7b152
    27 N7f87ab663db04cc6bc3b512f7be0b73f
    28 sg:journal.1133522
    29 schema:name Parallel heap: An optimal parallel priority queue
    30 schema:pagination 87-98
    31 schema:productId N20e6f4ae5ba749c8a0770b233641aee4
    32 N77e45f91b3da4299baf18d0bc8977e14
    33 Na7122a0062494b8da0746df58152050d
    34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007222595
    35 https://doi.org/10.1007/bf00128644
    36 schema:sdDatePublished 2019-04-11T13:56
    37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    38 schema:sdPublisher Nbecac9843f3448ac9d605a72969b4a01
    39 schema:url http://link.springer.com/10.1007/BF00128644
    40 sgo:license sg:explorer/license/
    41 sgo:sdDataset articles
    42 rdf:type schema:ScholarlyArticle
    43 N20e6f4ae5ba749c8a0770b233641aee4 schema:name doi
    44 schema:value 10.1007/bf00128644
    45 rdf:type schema:PropertyValue
    46 N2640a5a13e1f40f1a49fb26e64c7b152 schema:volumeNumber 6
    47 rdf:type schema:PublicationVolume
    48 N55b8dcec60154608bbd2ca7de1e3c469 rdf:first sg:person.012217451543.37
    49 rdf:rest rdf:nil
    50 N77e45f91b3da4299baf18d0bc8977e14 schema:name dimensions_id
    51 schema:value pub.1007222595
    52 rdf:type schema:PropertyValue
    53 N7f87ab663db04cc6bc3b512f7be0b73f schema:issueNumber 1
    54 rdf:type schema:PublicationIssue
    55 Na7122a0062494b8da0746df58152050d schema:name readcube_id
    56 schema:value 226713107096bdf855ccfee66a8a731b9987a1a9c1dd24bcd24d77099c53c7a3
    57 rdf:type schema:PropertyValue
    58 Nbecac9843f3448ac9d605a72969b4a01 schema:name Springer Nature - SN SciGraph project
    59 rdf:type schema:Organization
    60 Neba8a0c5cfe742cda0ab0814c1280377 rdf:first sg:person.010274011142.47
    61 rdf:rest N55b8dcec60154608bbd2ca7de1e3c469
    62 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    63 schema:name Information and Computing Sciences
    64 rdf:type schema:DefinedTerm
    65 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Computer Software
    67 rdf:type schema:DefinedTerm
    68 sg:journal.1133522 schema:issn 0920-8542
    69 1573-0484
    70 schema:name The Journal of Supercomputing
    71 rdf:type schema:Periodical
    72 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
    73 schema:familyName Deo
    74 schema:givenName Narsingh
    75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
    76 rdf:type schema:Person
    77 sg:person.012217451543.37 schema:affiliation https://www.grid.ac/institutes/grid.256304.6
    78 schema:familyName Prasad
    79 schema:givenName Sushil
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012217451543.37
    81 rdf:type schema:Person
    82 sg:pub.10.1007/bfb0036940 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028714319
    83 https://doi.org/10.1007/bfb0036940
    84 rdf:type schema:CreativeWork
    85 https://doi.org/10.1016/0020-0190(84)90128-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035509960
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1016/0020-0190(89)90138-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014637820
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.1016/b978-0-444-88071-0.50022-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007005196
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.1109/12.9744 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061089433
    92 rdf:type schema:CreativeWork
    93 https://doi.org/10.1109/32.29490 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061153847
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1109/ipps.1992.223004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086290914
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1109/tc.1980.1675680 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061532487
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1109/tse.1984.5010306 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061787736
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1109/wsc.1991.185670 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086305019
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1137/0215068 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841930
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1137/0217049 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842068
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1137/0218014 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842113
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1145/2514.2515 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015803283
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1145/63238.63249 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005973242
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1145/84537.84545 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031796676
    114 rdf:type schema:CreativeWork
    115 https://www.grid.ac/institutes/grid.170430.1 schema:alternateName University of Central Florida
    116 schema:name Computer Science Department, University of Central Florida, 32816, Orlando, FL, USA
    117 rdf:type schema:Organization
    118 https://www.grid.ac/institutes/grid.256304.6 schema:alternateName Georgia State University
    119 schema:name Mathematics and Computer Science Department, Georgia State University, 30303, Atlanta, GA, USA
    120 rdf:type schema:Organization
     




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


    ...