PRAM CREW parallel algorithms requiring logarithmic time and a linear number of processors exist for sliding (LZ1) and static dictionary compression. On the other hand, LZ2 compression seems hard to parallelize. Both adaptive methods work with prefix dictionaries, that is, all prefixes of a dictionary element are dictionary elements.Therefore, it is reasonable to use prefix dictionaries also for the static method. A left to right semi-greedy approach exists to compute an optimal parsing of a string with a prefix static dictionary. The left to right greedy approach is enough to achieve optimal compression with a sliding dictionary since such dictionary is both prefix and suffix. We assume the window is bounded by a constant. With the practical assumption that the dictionary elements have constant length we present PRAM EREW algorithms for sliding and static dictionary compression still requiring logarithmic time and a linear number of processors. A PRAM EREW decoder for static dictionary compression can be easily designed with a linear number of processors and logarithmic time. A work-optimal logarithmic time PRAM EREW decoder exists for sliding dictionary compression when the window has constant length. The simplest model for parallel computation is an array of processors with distributed memory and no interconnections, therefore, no communication cost. An approximation scheme to optimal compression with prefix static dictionaries was designed running with the same complexity of the previous algorithms on such model. It was presented for a massively parallel architecture but in virtue of its scalability it can be implemented on a small scale system as well. We describe such approach and extend it to the sliding dictionary method. The approximation scheme for sliding dictionaries is suitable for small scale systems but due to its adaptiveness it is practical for a large scale system when the file size is large. A two-dimensional extension of the sliding dictionary method to lossless compression of bi-level images, called block matching, is also discussed. We designed a parallel implementation of such heuristic on a constant size array of processors and experimented it with up to 32 processors of a 256 Intel Xeon 3.06 GHz processors machine (avogadro.cilea.it) on a test set of large topographic images. We achieved the expected speed-up, obtaining parallel compression and decompression about twenty-five times faster than the sequential ones.

A work-optimal O(lognlogM) time PRAM-EREW algorithm for lossless image compression by block matching was shown in L. Cinque et al., (2003), where n is the size of the image and M is the maximum size of the match. The design of a parallel decoder was left as an open problem. By slightly modifying the parallel encoder, in this paper we show how to implement the decoder in O(lognlogM) time with O(n/logn) processors on the PRAM-EREW. With the realistic assumption that the size of the compressed image is O(n1/2), the parallel decoder requires O(log2n) time and O(n/logn) processors on the mesh of trees

Summary form only given. In this paper, we showed a work-optimal parallel algorithm using the rectangle greedy matching technique requiring O (log M log n) time on the PRAM EREW model. We showed how algorithm is implemented on a mesh of trees still with optimal parallel work and in O (log M log n) time. Differently from arrays and trees, meshes of trees have both small diameter and large bisection width, which makes them as fast as hypercubic networks but simpler to build. In our case, we can even run the PRAM algorithm on the mesh of trees without slowing it down and without increasing the number of processors

Summary form only given. The unbounded version of the LZ2 compression method is P-complete, therefore, it is unlikely to have a sublinear work space when LZ2 compression is implemented unless a deletion heuristic is applied to bound the dictionary. Several LZ2 compression heuristics have been designed and several deletion heuristics have been applied. In this work, we show experimental results on the compression effectiveness for 2/spl les/p/spl les/6, using the AP compression heuristic. The relaxed LRU (RLRU) deletion heuristic turns out to be as good as LRU even when p is equal to 2. This fact shows that there should be always an improvement when the two values of p differ substantially. FREEZE, RESTART and SWAP are simpler heuristics, which do not delete elements from the dictionary at each step. SWAP is the best among these simpler approaches and has a worse compression efficiency than RLRU and LRU.

The bottom-up hierarchical clustering methodology that is introduced in this paper is an extension of self-organizing map neural network (ESOM) and it provides remedy for two different major problems. The first one is related to the hierarchical clustering and the second one is related to the self-organizing map (SOM) neural network that is able to perform a clustering task. The crucial problem that the hierarchical clustering approaches (top-down and bottom-up) are faced with is the fact that once a merging or decomposing of two clusters takes place, it is impossible to undo or redo it. The crucial problem for SOM stems from the fact that the initial clusters' weight vectors, that are generated randomly, highly influence the outcome of the SOM clustering.

In this paper, we show a simple lossless compression heuristic for color images in RGB format. The main advantage of this approach is that it provides a highly parallelizable compressor and decompressor. The lossless image compression methods often consist of two distinct and independent components (context-based methods): modeling and coding phase. It can be applied independently to each block of 8/spl times/8 pixels achieving 70 to 80 percent of the compression obtained with LOCO-I (JPEG-LS).

Summary form only given. The parallel complexity of LZ compression and decompression has been studied. Parallel algorithms have been designed for LZ1 compression and decompression. LZ2 compression is hardly parallelizable, since it is P-complete. A nearly work-optimal parallel decoding algorithm was shown which run on the PRAM EREW in O(log n) time with O(n/(log n)/sup 1/2 /) processors for text compressed with LZ1 and LZ2 methods. Pseudo work-optimal PRAM EREW decoders for finite window compression and LZ2 compression requiring logarithmic time with O(dn) work are presented. Finally, the PRAM EREW decoders requiring logarithmic time and O(n/log n) processors were observed that are possible with the non-conservative assumption. The algorithms employed the Euler tour technique and parallel integer sorting.

Summary form only given. We show a parallel algorithm using a rectangle greedy matching technique which requires a linear number of processors and O(log(M)log(n)) time on the PRAM EREW model. The algorithm is suitable for practical parallel architectures as a mesh of trees, a pyramid or a multigrid. We implement a sequential procedure which simulates the compression performed by the parallel algorithm and it achieves 95 to 97 percent of the compression of a previous sequential heuristic. To achieve logarithmic time we partition an m/spl times/n image, I, in x/spl times/y rectangular areas where x and y are /spl Theta/(log/sup 1/2 / mn). In parallel for each area, one processor applies the sequential parsing algorithm, so that, in logarithmic time, each area is parsed in rectangles, some of which are monochromatic. Before encoding, we compute larger monochromatic rectangles by merging the ones adjacent on the horizontal boundaries and then on the vertical boundaries, doubling in this way the length and width of each area at each step.

The LZ2 compression method seems hardly parallelizable since some related heuristics are known to be P-complete. In spite of such a negative result, the algorithm process can be parallelized efficiently. In this paper, we show a work-optimal parallel decoding Las Vegas algorithm for text compressed by standard implementation of the LZ2 algorithm (next character heuristic). The algorithm works in expected logarithmic time on a PRAM CRCW. We also address a different implementation called the identity heuristic. In this case we need to make the realistic assumption that the length of the dictionary elements is logarithmic in order to decode with optimal parallel work. The algorithm takes deterministic logarithmic time on a PRAM CREW.

While sliding window (LZ1) compression can be parallelized efficiently, the LZ2 compression method seems hardly parallelizable since some related heuristics are known to be P-complete. In spite of such negative result, there are parallel decoders which run in O(log/sup 2/ n) time with O(n/log n) processors on the PRAM EREW where n is the length of the output string, as for LZ1 decompression. We show a faster parallel decoding algorithm which runs on the PRAM EREW in O(log n) time with O(n) processors for text compressed by a standard implementation of the LZ2 algorithm (next character heuristic). We observe that LZ1 parallel decoders also can have such speed up. Moreover, we address a different implementation of LZ2 compression called identity heuristic. In this case, decoding on the PRAM EREW takes O(log n log log n) time with O(n/log n) processors with the realistic assumption that the length of the dictionary elements is logarithmic.

We show an O(m+t) space algorithm to find all the occurrences of a pattern in a text compressed with the ID heuristic that runs in time O(n(m+t)), where m is the pattern length, n is the size of the compressed text and 1 is the maximum target length.

We consider sublinear massively parallel algorithms for compressing text with respect to a static dictionary. Algorithms for the PRAM model can do this optimally in O(m+log(n)) time with n processors, where m is the length of the longest entry in the dictionary and n is the length of the input string. We consider what is perhaps the most practical model of massively parallel computation imaginable: a linear array of processors where each processor is connected only to its left and right neighbors. We present an algorithm which in time O(km+mlog(m)) with n/(km) processors is guaranteed to be within a factor of (k+1)/k of optimal, for any integer k/spl ges/1. We also present experiments indicating that performance may be even better in practice.

The authors study parallel algorithms for lossless data compression via textual substitution. Dynamic dictionary compression is known to be P-complete, however, if the dictionary is given in advance, they show that compression can be efficiently parallelized and a computational advantage is obtained when the dictionary has the prefix property. The approach can be generalized to the sliding window method where the dictionary is a window that passes continuously from left to right over the input string.>