pipette
ESEspañol

Massively Parallel Algorithms for Huffman Coding

Masoud Seddighin, Saeed Seddighin

PreprintClaims a big step

In the authors' words

Huffman coding is one of the oldest and most fundamental problems in computer science. Given a string of length over a general alphabet, the goal is to assign a binary codeword to each character so that no codeword is a prefix of another and the total encoded length of the string is minimized. Huffman coding is widely used in practical compression systems, including file compression. As modern datasets continue to grow, it is natural to study whether a Huffman code can be constructed efficiently in the massively parallel computation (\MPC) model. The celebrated Huffman coding algorithm admits two straightforward \MPC implementations: for any constant , one uses memory per machine but requires rounds, while the other runs in rounds but requires memory per machine. We give the first nontrivial \MPC algorithm for Huffman coding that bypasses both limitations. For every constant , our algorithm uses rounds and memory per machine, while its total memory and total computation are . This provides a rare example in which an exact solution to a problem whose classical algorithm is sequential in nature can be obtained in a sublogarithmic number of \MPC rounds.

Main resultThe abstract does not state a limitation.

In plain words AI summary

Two basic parallel methods exist: one needs many rounds but little memory, the other needs few rounds but much memory. The authors created a new algorithm that uses few rounds and little memory at the same time. Their method runs in O(log log n) rounds with O(n^ε) memory per machine for any small constant ε.

Written by Kimi K2.5 using only the abstract above. Jev checked that every sentence is supported by the abstract sentences it cites, and removed any that were not. Point at a sentence to highlight its source. 2 sentences were removed for not being supported by the abstract.

Appeared: Thursday, October 8. arXiv. Preprint, not yet peer-reviewed.