Average-Case Communication-Optimal Parallel Parenthesis Matching View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-11-08

AUTHORS

Chun-Hsi Huang , Xin He

ABSTRACT

We provide the first non-trivial lower bound, p-3/p · n/p, where p is the number of the processors and n is the data size, on the average-case communication volume, σ, required to solve the parenthesis matching problem and present a parallel algorithm that takes linear (optimal) computation time and optimal expected message volume, σ +p.The kernel of the algorithm is to solve the all nearest smaller values problem. Provided n/p = Ω(p), we present an algorithm that achieves optimal sequential computation time and uses only a constant number of communication phases, with the message volume in each phase bounded above by (n/p +p) in the worst case and p in the average case, assuming the input instances are uniformly distributed. More... »

PAGES

308-319

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-36136-7_28

DOI

http://dx.doi.org/10.1007/3-540-36136-7_28

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineerin, University of Connecticut, 06269, Storrs, CT", 
          "id": "http://www.grid.ac/institutes/grid.63054.34", 
          "name": [
            "Department of Computer Science and Engineerin, University of Connecticut, 06269, Storrs, CT"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Huang", 
        "givenName": "Chun-Hsi", 
        "id": "sg:person.01155773776.53", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01155773776.53"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY", 
          "id": "http://www.grid.ac/institutes/grid.273335.3", 
          "name": [
            "Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY"
          ], 
          "type": "Organization"
        }, 
        "familyName": "He", 
        "givenName": "Xin", 
        "id": "sg:person.011352641523.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-11-08", 
    "datePublishedReg": "2002-11-08", 
    "description": "We provide the first non-trivial lower bound, p-3/p \u00b7 n/p, where p is the number of the processors and n is the data size, on the average-case communication volume, \u03c3, required to solve the parenthesis matching problem and present a parallel algorithm that takes linear (optimal) computation time and optimal expected message volume, \u03c3 +p.The kernel of the algorithm is to solve the all nearest smaller values problem. Provided n/p = \u03a9(p), we present an algorithm that achieves optimal sequential computation time and uses only a constant number of communication phases, with the message volume in each phase bounded above by (n/p +p) in the worst case and p in the average case, assuming the input instances are uniformly distributed.", 
    "editor": [
      {
        "familyName": "Bose", 
        "givenName": "Prosenjit", 
        "type": "Person"
      }, 
      {
        "familyName": "Morin", 
        "givenName": "Pat", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-36136-7_28", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-00142-3", 
        "978-3-540-36136-7"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "computation time", 
      "message volume", 
      "nearest smaller values problem", 
      "sequential computation time", 
      "parenthesis matching problem", 
      "linear computation time", 
      "data size", 
      "parallel algorithm", 
      "communication volume", 
      "communication phases", 
      "input instances", 
      "parenthesis matching", 
      "matching problem", 
      "average case", 
      "algorithm", 
      "constant number", 
      "worst case", 
      "processors", 
      "matching", 
      "kernel", 
      "instances", 
      "number", 
      "time", 
      "volume", 
      "cases", 
      "size", 
      "phase", 
      "value problem", 
      "problem", 
      "p-3/p", 
      "average-case communication volume", 
      "smaller values problem", 
      "optimal sequential computation time", 
      "Average-Case Communication-Optimal Parallel Parenthesis Matching", 
      "Communication-Optimal Parallel Parenthesis Matching", 
      "Parallel Parenthesis Matching"
    ], 
    "name": "Average-Case Communication-Optimal Parallel Parenthesis Matching", 
    "pagination": "308-319", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1023140152"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-36136-7_28"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-36136-7_28", 
      "https://app.dimensions.ai/details/publication/pub.1023140152"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:47", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_147.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-36136-7_28"
  }
]
 

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/3-540-36136-7_28'

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/3-540-36136-7_28'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-36136-7_28'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-36136-7_28'


 

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

111 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-36136-7_28 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N19e2b33146884647aecd36231b3b541b
4 schema:datePublished 2002-11-08
5 schema:datePublishedReg 2002-11-08
6 schema:description We provide the first non-trivial lower bound, p-3/p · n/p, where p is the number of the processors and n is the data size, on the average-case communication volume, σ, required to solve the parenthesis matching problem and present a parallel algorithm that takes linear (optimal) computation time and optimal expected message volume, σ +p.The kernel of the algorithm is to solve the all nearest smaller values problem. Provided n/p = Ω(p), we present an algorithm that achieves optimal sequential computation time and uses only a constant number of communication phases, with the message volume in each phase bounded above by (n/p +p) in the worst case and p in the average case, assuming the input instances are uniformly distributed.
7 schema:editor N5822ea5dfdb04657bc353c6c9b4531cc
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nb423bf94a90042be8a06f4f1671b6b45
12 schema:keywords Average-Case Communication-Optimal Parallel Parenthesis Matching
13 Communication-Optimal Parallel Parenthesis Matching
14 Parallel Parenthesis Matching
15 algorithm
16 average case
17 average-case communication volume
18 cases
19 communication phases
20 communication volume
21 computation time
22 constant number
23 data size
24 input instances
25 instances
26 kernel
27 linear computation time
28 matching
29 matching problem
30 message volume
31 nearest smaller values problem
32 number
33 optimal sequential computation time
34 p-3/p
35 parallel algorithm
36 parenthesis matching
37 parenthesis matching problem
38 phase
39 problem
40 processors
41 sequential computation time
42 size
43 smaller values problem
44 time
45 value problem
46 volume
47 worst case
48 schema:name Average-Case Communication-Optimal Parallel Parenthesis Matching
49 schema:pagination 308-319
50 schema:productId N139c0da3dd89480da844368fc2256723
51 N3d5996f748114558a08b91da843ec92c
52 schema:publisher N78e386bee7594091bd4284b56ef313f0
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023140152
54 https://doi.org/10.1007/3-540-36136-7_28
55 schema:sdDatePublished 2021-11-01T18:47
56 schema:sdLicense https://scigraph.springernature.com/explorer/license/
57 schema:sdPublisher Nbbaf05218274424bb04708bae47a3269
58 schema:url https://doi.org/10.1007/3-540-36136-7_28
59 sgo:license sg:explorer/license/
60 sgo:sdDataset chapters
61 rdf:type schema:Chapter
62 N0c29e94c8eae4994a9c36f903838cd97 schema:familyName Morin
63 schema:givenName Pat
64 rdf:type schema:Person
65 N139c0da3dd89480da844368fc2256723 schema:name doi
66 schema:value 10.1007/3-540-36136-7_28
67 rdf:type schema:PropertyValue
68 N19e2b33146884647aecd36231b3b541b rdf:first sg:person.01155773776.53
69 rdf:rest Nc583fe75f1e341dd83c655df7a2c1019
70 N2dba1121128347a3a55608b002cd4f25 schema:familyName Bose
71 schema:givenName Prosenjit
72 rdf:type schema:Person
73 N3d5996f748114558a08b91da843ec92c schema:name dimensions_id
74 schema:value pub.1023140152
75 rdf:type schema:PropertyValue
76 N5822ea5dfdb04657bc353c6c9b4531cc rdf:first N2dba1121128347a3a55608b002cd4f25
77 rdf:rest Ncc9fe625c6224cc3ac413fdb705b9181
78 N78e386bee7594091bd4284b56ef313f0 schema:name Springer Nature
79 rdf:type schema:Organisation
80 Nb423bf94a90042be8a06f4f1671b6b45 schema:isbn 978-3-540-00142-3
81 978-3-540-36136-7
82 schema:name Algorithms and Computation
83 rdf:type schema:Book
84 Nbbaf05218274424bb04708bae47a3269 schema:name Springer Nature - SN SciGraph project
85 rdf:type schema:Organization
86 Nc583fe75f1e341dd83c655df7a2c1019 rdf:first sg:person.011352641523.42
87 rdf:rest rdf:nil
88 Ncc9fe625c6224cc3ac413fdb705b9181 rdf:first N0c29e94c8eae4994a9c36f903838cd97
89 rdf:rest rdf:nil
90 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
91 schema:name Mathematical Sciences
92 rdf:type schema:DefinedTerm
93 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
94 schema:name Numerical and Computational Mathematics
95 rdf:type schema:DefinedTerm
96 sg:person.011352641523.42 schema:affiliation grid-institutes:grid.273335.3
97 schema:familyName He
98 schema:givenName Xin
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011352641523.42
100 rdf:type schema:Person
101 sg:person.01155773776.53 schema:affiliation grid-institutes:grid.63054.34
102 schema:familyName Huang
103 schema:givenName Chun-Hsi
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01155773776.53
105 rdf:type schema:Person
106 grid-institutes:grid.273335.3 schema:alternateName Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY
107 schema:name Department of Computer Science and Engineering, State University of New York at Buffalo, 14260, Buffalo, NY
108 rdf:type schema:Organization
109 grid-institutes:grid.63054.34 schema:alternateName Department of Computer Science and Engineerin, University of Connecticut, 06269, Storrs, CT
110 schema:name Department of Computer Science and Engineerin, University of Connecticut, 06269, Storrs, CT
111 rdf:type schema:Organization
 




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


...