Massively Parallel Algorithms for Huffman Coding
En palabras de los autores
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.
En palabras simples Resumen con IA
Existen dos métodos paralelos básicos: uno necesita muchas rondas pero poca memoria, el otro necesita pocas rondas pero mucha memoria. Los autores crearon un nuevo algoritmo que usa pocas rondas y poca memoria al mismo tiempo. Su método se ejecuta en O(log log n) rondas con O(n^ε) memoria por máquina para cualquier constante ε pequeña.
Escrito por Kimi K2.5 usando solo el abstract de arriba. Jev verificó que cada oración esté respaldada por las oraciones del abstract que cita y eliminó las que no. Pasá el cursor por una oración para ver de dónde sale. Se eliminaron 2 oraciones por no estar respaldadas por el abstract.
Apareció: jueves, 8 de octubre. arXiv. Preprint, todavía sin revisión por pares.