Approximating Huffman Codes in Parallel View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-06-25

AUTHORS

Piotr Berman , Marek Karpinski , Yakov Nekrich

ABSTRACT

In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work.Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) and with n processors. This represents a useful improvement since most practical situations satisfy H = O(logn). More... »

PAGES

845-855

Book

TITLE

Automata, Languages and Programming

ISBN

978-3-540-43864-9
978-3-540-45465-6

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45465-9_72

DOI

http://dx.doi.org/10.1007/3-540-45465-9_72

DIMENSIONS

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


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": "Dept. of Computer Science, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept.of Computer Science and Engineering, The Pennsylvania State University, USA", 
            "Dept. of Computer Science, University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Karpinski", 
        "givenName": "Marek", 
        "id": "sg:person.011636042271.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Computer Science, University of Bonn, Germany", 
          "id": "http://www.grid.ac/institutes/grid.10388.32", 
          "name": [
            "Dept. of Computer Science, University of Bonn, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nekrich", 
        "givenName": "Yakov", 
        "id": "sg:person.014556642366.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-06-25", 
    "datePublishedReg": "2002-06-25", 
    "description": "In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work.Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) and with n processors. This represents a useful improvement since most practical situations satisfy H = O(logn).", 
    "editor": [
      {
        "familyName": "Widmayer", 
        "givenName": "Peter", 
        "type": "Person"
      }, 
      {
        "familyName": "Eidenbenz", 
        "givenName": "Stephan", 
        "type": "Person"
      }, 
      {
        "familyName": "Triguero", 
        "givenName": "Francisco", 
        "type": "Person"
      }, 
      {
        "familyName": "Morales", 
        "givenName": "Rafael", 
        "type": "Person"
      }, 
      {
        "familyName": "Conejo", 
        "givenName": "Ricardo", 
        "type": "Person"
      }, 
      {
        "familyName": "Hennessy", 
        "givenName": "Matthew", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45465-9_72", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-43864-9", 
        "978-3-540-45465-6"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "first parallel algorithm", 
      "Huffman codes", 
      "parallel algorithm", 
      "n processors", 
      "Huffman tree", 
      "logarithmic time", 
      "parallel construction", 
      "algorithm", 
      "initial set", 
      "linear work", 
      "most practical situations", 
      "code", 
      "practical situations", 
      "processors", 
      "useful improvement", 
      "optimal time", 
      "work", 
      "set", 
      "parallel", 
      "trees", 
      "time", 
      "situation", 
      "construction", 
      "improvement", 
      "length h", 
      "results", 
      "new results", 
      "elements", 
      "paper", 
      "problem", 
      "approach"
    ], 
    "name": "Approximating Huffman Codes in Parallel", 
    "pagination": "845-855", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1042338177"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45465-9_72"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45465-9_72", 
      "https://app.dimensions.ai/details/publication/pub.1042338177"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-08-04T17:20", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_406.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45465-9_72"
  }
]
 

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-45465-9_72'

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-45465-9_72'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45465-9_72'

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-45465-9_72'


 

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

130 TRIPLES      22 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45465-9_72 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Nc2033dbb058248e0899712a65f5ab738
4 schema:datePublished 2002-06-25
5 schema:datePublishedReg 2002-06-25
6 schema:description In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work.Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) and with n processors. This represents a useful improvement since most practical situations satisfy H = O(logn).
7 schema:editor Na71a7203e09e449e8fa3177ec390dab6
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nd8eb9179b87243f49240abbe308b3be8
11 schema:keywords Huffman codes
12 Huffman tree
13 algorithm
14 approach
15 code
16 construction
17 elements
18 first parallel algorithm
19 improvement
20 initial set
21 length h
22 linear work
23 logarithmic time
24 most practical situations
25 n processors
26 new results
27 optimal time
28 paper
29 parallel
30 parallel algorithm
31 parallel construction
32 practical situations
33 problem
34 processors
35 results
36 set
37 situation
38 time
39 trees
40 useful improvement
41 work
42 schema:name Approximating Huffman Codes in Parallel
43 schema:pagination 845-855
44 schema:productId N2cedb73c96ca4c7a9efbb3e67dbd325a
45 N7eb6d7cb36f34a189c038c44c902b1cc
46 schema:publisher Ne74df146a52445f08a4fe027f759f5c7
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042338177
48 https://doi.org/10.1007/3-540-45465-9_72
49 schema:sdDatePublished 2022-08-04T17:20
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher Nc4082ce50172470c821271f0c168581a
52 schema:url https://doi.org/10.1007/3-540-45465-9_72
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N03b930f9fd40484d9429a4d6413b43f1 rdf:first Ne7a50a54f9754e91b5abc5e4cf03ed50
57 rdf:rest Nec0e794812db4080b1922f9f8bd42aec
58 N289e6914c55a4f618d8c7b15e59c3410 schema:familyName Widmayer
59 schema:givenName Peter
60 rdf:type schema:Person
61 N2cedb73c96ca4c7a9efbb3e67dbd325a schema:name dimensions_id
62 schema:value pub.1042338177
63 rdf:type schema:PropertyValue
64 N44ede5d8c246440f9a062a889f20d170 schema:familyName Eidenbenz
65 schema:givenName Stephan
66 rdf:type schema:Person
67 N49c1f0ddcd2648dda4c71e927097a87a schema:familyName Hennessy
68 schema:givenName Matthew
69 rdf:type schema:Person
70 N7eb6d7cb36f34a189c038c44c902b1cc schema:name doi
71 schema:value 10.1007/3-540-45465-9_72
72 rdf:type schema:PropertyValue
73 N82e7d04c51a84bbd926eeb4a9ee7f6e4 schema:familyName Triguero
74 schema:givenName Francisco
75 rdf:type schema:Person
76 N8557c09ca9d041109311169ab686a88a rdf:first N82e7d04c51a84bbd926eeb4a9ee7f6e4
77 rdf:rest N03b930f9fd40484d9429a4d6413b43f1
78 N923bc24849da4a36aedb5805aeb1c342 rdf:first sg:person.011636042271.02
79 rdf:rest Nf7eb807d259f4c85b939e2fc949b40a6
80 N9fe62e454648446d9f82a291b99830b2 rdf:first N44ede5d8c246440f9a062a889f20d170
81 rdf:rest N8557c09ca9d041109311169ab686a88a
82 Na71a7203e09e449e8fa3177ec390dab6 rdf:first N289e6914c55a4f618d8c7b15e59c3410
83 rdf:rest N9fe62e454648446d9f82a291b99830b2
84 Nc2033dbb058248e0899712a65f5ab738 rdf:first sg:person.01274506210.27
85 rdf:rest N923bc24849da4a36aedb5805aeb1c342
86 Nc4082ce50172470c821271f0c168581a schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 Nc7f211f62e534c79a576f6f1964ef353 schema:familyName Conejo
89 schema:givenName Ricardo
90 rdf:type schema:Person
91 Nd8eb9179b87243f49240abbe308b3be8 schema:isbn 978-3-540-43864-9
92 978-3-540-45465-6
93 schema:name Automata, Languages and Programming
94 rdf:type schema:Book
95 Ne74df146a52445f08a4fe027f759f5c7 schema:name Springer Nature
96 rdf:type schema:Organisation
97 Ne7a50a54f9754e91b5abc5e4cf03ed50 schema:familyName Morales
98 schema:givenName Rafael
99 rdf:type schema:Person
100 Nec0e794812db4080b1922f9f8bd42aec rdf:first Nc7f211f62e534c79a576f6f1964ef353
101 rdf:rest Nf3ab94f8cf75492dacafd10ae751a938
102 Nf3ab94f8cf75492dacafd10ae751a938 rdf:first N49c1f0ddcd2648dda4c71e927097a87a
103 rdf:rest rdf:nil
104 Nf7eb807d259f4c85b939e2fc949b40a6 rdf:first sg:person.014556642366.63
105 rdf:rest rdf:nil
106 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
107 schema:name Mathematical Sciences
108 rdf:type schema:DefinedTerm
109 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
110 schema:name Numerical and Computational Mathematics
111 rdf:type schema:DefinedTerm
112 sg:person.011636042271.02 schema:affiliation grid-institutes:grid.10388.32
113 schema:familyName Karpinski
114 schema:givenName Marek
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011636042271.02
116 rdf:type schema:Person
117 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.10388.32
118 schema:familyName Berman
119 schema:givenName Piotr
120 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
121 rdf:type schema:Person
122 sg:person.014556642366.63 schema:affiliation grid-institutes:grid.10388.32
123 schema:familyName Nekrich
124 schema:givenName Yakov
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014556642366.63
126 rdf:type schema:Person
127 grid-institutes:grid.10388.32 schema:alternateName Dept. of Computer Science, University of Bonn, Germany
128 schema:name Dept. of Computer Science, University of Bonn, Germany
129 Dept.of Computer Science and Engineering, The Pennsylvania State University, USA
130 rdf:type schema:Organization
 




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


...