Name
Abstract | ||
|---|---|---|
We present a novel lossless universal source coding algorithm that uses parallel computational units to increase the throughput. The length-N input sequence is partitioned into B blocks. Processing each block independently of the other blocks can accelerate the computation by a factor of B, but degrades the compression quality. Instead, our approach is to first estimate the minimum description length (MDL) source underlying the entire input, and then encode each of the B blocks in parallel based on the MDL source. With this two-pass approach, the compression loss incurred by using more parallel units is insignificant. Our algorithm is work-efficient, i.e., its computational complexity is O(N=B). Its redundancy is approximately B log(N=B) bits above Rissanen's lower bound on universal coding performance, with respect to any tree source whose maximal depth is at most log(N=B). |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/ISIT.2014.6875156 | Information Theory |
Keywords | DocType | Volume |
source coding,trees (mathematics),computational complexity,length-N input sequence,minimum description length,novel lossless universal source coding algorithm,parallel computational units,parallel two-pass MDL context tree algorithm,two-pass approach,MDL,computational complexity,data compression,parallel algorithms,redundancy,universal source coding,work-efficient algorithms | Journal | abs/1405.6322 |
Citations | PageRank | References |
1 | 0.36 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nikhil Krishnan | 1 | 6 | 1.46 |
| Dror Baron | 2 | 768 | 77.65 |
| Mehmet Kivanç Mihçak | 3 | 265 | 23.84 |