NDLI: Practical Parallel Algorithms for Dictionary Data Compression

Content Provider	IEEE Xplore Digital Library
Author	Cinque, L. De Agostino, S. Lombardi, L.
Copyright Year	2009
Abstract	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 distibuted 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.
Starting Page	441
Ending Page	441
File Size	97375
Page Count	1
File Format	PDF
ISBN	9781424437535
ISSN	10680314
DOI	10.1109/DCC.2009.84
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-03-16
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Parallel algorithms Dictionaries Data compression Phase change random access memory Decoding Image coding Computational modeling Concurrent computing Distributed computing Costs scalability lossless compression static dictionary sliding window array architecture
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in