loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Data Compression Conference (DCC '95)
Near optimal compression with respect to a static dictionary on a practical massively parallel architecture
Snowbird, Utah
March 28-March 30
ISBN: 0-8186-7012-6
ASCII Text
x 
 
D. Belinskaya, S. DeAgostino, J.A. Storer, "Near optimal compression with respect to a static dictionary on a practical massively parallel architecture," Data Compression Conference, pp. 172, Data Compression Conference (DCC '95), 1995.
 
 
BibTex
x
 
@article{ 10.1109/DCC.1995.515507,
author = {D. Belinskaya and S. DeAgostino and J.A. Storer},
title = {Near optimal compression with respect to a static dictionary on a practical massively parallel architecture},
journal ={Data Compression Conference},
volume = {0},
year = {1995},
isbn = {0-8186-7012-6},
pages = {172},
doi = {http://doi.ieeecomputersociety.org/10.1109/DCC.1995.515507},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Data Compression Conference
TI - Near optimal compression with respect to a static dictionary on a practical massively parallel architecture
SN - 0-8186-7012-6
SP
EP
A1 - D. Belinskaya,
A1 - S. DeAgostino,
A1 - J.A. Storer,
PY - 1995
KW - parallel algorithms; parallel architectures; word processing; data compression; computational complexity; random-access storage; near optimal compression; static dictionary; practical massively parallel architecture; sublinear massively parallel algorithms; text compression; PRAM model; input string; massively parallel computation; linear array
VL - 0
JA - Data Compression Conference
ER -
 
D. Belinskaya, Dept. of Comput. Sci., Brandeis Univ., Waltham, MA, USA
S. DeAgostino, Dept. of Comput. Sci., Brandeis Univ., Waltham, MA, USA
J.A. Storer, Dept. of Comput. Sci., Brandeis Univ., Waltham, MA, USA
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.
Index Terms:
parallel algorithms; parallel architectures; word processing; data compression; computational complexity; random-access storage; near optimal compression; static dictionary; practical massively parallel architecture; sublinear massively parallel algorithms; text compression; PRAM model; input string; massively parallel computation; linear array
Citation:
D. Belinskaya, S. DeAgostino, J.A. Storer, "Near optimal compression with respect to a static dictionary on a practical massively parallel architecture," dcc, pp.172, Data Compression Conference (DCC '95), 1995
Usage of this product signifies your acceptance of the Terms of Use.