NSF Publications

Publications

Text Compression and Fast Retrieval
Image Compression
Bioinformatics

Robert Franceschini, Amar Mukherjee, "Data Compression Using Encrypted Text", Proceedings of the Third Forum on Research and Technology, Advances in Digital Libraries, ADL96, May 13-15 1996, pp 130-138.
Tao Tao, Amar Mukherjee and Ravi Vijaya Satya, "A search-aware JPEG-LS Variation for Compressed Image Retrieval", International Symposium on Intelligent Multimedia, Video & Speech Processing. October 20-22, 2004.
Nan Zhang, Tao Tao, Ravi Vijaya Satya, and Amar Mukherjee"Modified LZW algorithm for efficient compressed text retrieval", International conference on information technology: coding and computing, Las Vegas, Nevada. 2004.

Tao Tao, Amar Mukherjee, "LZW based compressed pattern matching", DCC 2004, snowbird, Utah, March 2004.

Tao Tao, Amar Mukherjee, "Compressed Pattern Matching for Predictive Lossless Image Encoding", DMS2003, Miami, FL. Sept. 24-26, 2003.

Ravi Vijaya Satya, Amar Mukherjee, Uday Kumar Ranga, "A Pattern Matching Algorithm for Codon Optimization and CpG Motif-Engineering in DNA Expression Vectors", CSB 2003, Stanford, CA; Aug 11-14 2003.

Weifeng Sun, Amar Mukherjee, Nan Zhang, "Dictionary-Based Fast Transform for Text Compression", Proceedings of International Conference on Information and Theory : Coding and Computing, IEEE Computer Society, Las Vegas, Nevada, April 2003. (Presentation slide)

Nan Zhang, Amar Mukherjee, Don Adjeroh, Tim Bell, "Approximate Pattern Matching Using the Burrows-Wheeler Transform", (full paper), Proceedings of Data Compression Conference, Snowbird, Utah, March 2003.

Weifeng Sun, Amar Mukherjee, Nan Zhang, "A Dictionary-Based Multi-Corpora Text Compression System", Proceedings of Data Compression Conference, Snowbird, Utah, March 2003.

Donald A. Adjeroh, Tim Bell, Matt Powell, Nan Zhang, Amar Mukherjee, "Pattern Matching in BWT-Transformed Text", Proceedings of Data Compression Conference, Snowbird, Utah, Apr 2002.

A. Mukherjee, N. Motgi (University of Central Florida), J. Becker, A. Friebe, C. Habermann (Darmstadt University of Technology) "Prototyping of Efficient Hardware Algorithms for Data Compression in Future Communication Systems", International workshop on Rapid System Prototyping 2001, Monterey Beach Resort, Californica, June 25-27, 2001.

F. Awan and A. Mukherjee, "LIPT: A Lossless Text Transform to improve compression", Proceedings of International Conference on Information and Theory : Coding and Computing, IEEE Computer Society, Las Vegas, Nevada, 2001.

N. Motgi and A. Mukherjee, "Network Conscious Text Compression Systems (NCTCSys)" publication in the Proceedings of International Conference on Information and Theory : Coding and Computing, IEEE Computer Society, Las Vegas, Nevada, 2001

F. Awan, Nan Zhang, N. Motgi, R. Iqbal and A. Mukherjee, "A New Text Preprocessing Algorithm for bzip2 and PPM*", Proceedings of Data Compression Conference, Snowbird, Utah, March 2001.

N. Zhang, A. Mukherjee, D. Adjeroh, T. Bell "Approximate pattern matching using Burrows-Wheeler Transform", Proc. Data Compression Conference, Page# 458, 2003.

T. Tao and A. Mukherjee, "Compressed Pattern Matching for Predictive Lossless Image Encoding", Proc. Internaltional Conference on Distributed Multimedia Systems, page# 120, 2004.

N. Zhang, T. Tao, R.V. Satya and Amar Mukherjee "Modified LZW Algorithm for Efficient Compressed Text Retrieval", Proc. International Conference on Information Technology, page# 224, 2004.

T. Tao and Amar Mukherjee "Compressed Pattern Matching for Predictive Lossless Image Encoding", Proc. International Conference on Distributed Multimedia Systems, page# 120, 2004.

T. Tao and Amar Mukherjee "LZW based compressed pattern matching", Proc. Data Compression Conference, page# 568, 2004.

Tim Bell, Andrew Firth, Amar Mukherjee and Donald Adjeroh "A Comparison of BWT Approaches to String Patterm Matching", Software-Practice and Experience, page# 1217, Vol. 35, 2005.

T. Tao and Amar Mukherjee "Multiple-Pattern Matching in LZW Compressed Files Using Aho-Corasick Algorithm", Proc. Data Compression Conference, page# 482, 2005.

T. Tao and Amar Mukherjee "Pattern Matching in LZW Compressed Files", IEEE Transaction on Computers, page# 929-938, Vol. 54, No. 8, August 2005.

T. Tao and Amar Mukherjee "Multiple-Pattern Matching in LZW Compressed Files", Proc. International International Conference on Information Technology, Coding and Computing, page# 91, Vol. 1, 2005.

Nan Zhang "Transform Based and Search Aware Text Compression Schemes and Compressed Domain Text Retrieval", Doctoral Dissertation, University of Central Florida, 2005.

Tao Tao "Compressed Pattern Matching for Text and Images", Doctoral Dissertation, University of Central Florida, 2005.

Ravi Vijaya Satya "Algorithms for Haplotype Inference and Block Partitioning", Doctoral Dissertation, University of Central Florida, 2006.

Weifeng Sun "Wavelets in Real-Time Rendering", Doctoral Dissertation, University of Central Florida, 2006.

R. Vijaya and Amar Mukherjee "An optimal algorithm for perfect phylogeny haplotyping", Journal of Computational Biology, page# 897, Vol. 13, 2006.

R. Vijaya and Amar Mukherjee "The Undirected Incomplete Perfect Phylogeny Problem", IEEE/ACM Transaction on Computational Biology and Bioinformatics, Vol. 5, 2006.

Weifeng Sun and Amar Mukherjee "Generalized Wavelet Product Integral for Rendering Dynamic Glossy Objects", ACM SIGGRAPH 2006, Transaction on Graphics, Vol. 25, 2006.

Ravi Vijaya Satya, Amar Mukherjee, Gabriela Alexe, Laxmi Parida, and Gyan Bhanot "Constructing Near-Perfect Phylogenies with multiple homoplasy events", Bioinformatics, Vol. 22, p. 514, 2006.

Old Papers

Preprocessing Text to Improve Compression Ratios
Holger Kruse, Amar Mukherjee
Abstract:
In this paper we discuss the use of a text preprocessing algorithm that can improve the compression ratio of standard data compression algorithms, in particular 'bzip2' when used on text files.
The text preprocessing algorithm uses a static dicitonary of the english language that is kept seperately from the compressed file. The method in which the dictionary is used by the algorithm to transform the text is based on published earlier.

Improve Text Compression Ratios with the Burrows-Wheeler Transform
Holger Kruse, Amar Mukherjee
Abstract:
In this paper we describe several methods that can be used to improve the compression ration of compression algorithms based on the Burrows-Wheeler Transform, as, for instance, implemented in 'bzip2', when used in combination with English language text files.
We first briefly describe the Burrows-Wheeler Transform and some of its strenghts and weakness, and motivate enhancements to the exisiting algorithm, specifically for the purpose of text compression. We then describe our implementation of these enhancements and test results, compared to the original algorithm.
Algorithms for Text and Image Compression
Amar Mukherjee, Holger Kruse, Kunal Mukherjee
Abstract:
The primary objective of data compression algorithms is to reduce redundancy in data representation in order to decrease data storage requirement. Data compression also offers an attractive approach to reduce the communication cost by effectively utilizing the available bandwidth in the data links. In the nineties, we have seen an unprecedented explosion of digital data on the information superhighways of the world. This data represents a variety of objects from the multimedia spectrum such as text, images, video, sound, computer programs, graphs,charts,maps,tables.....

Recursive Merge-Filter Algorithm for Computing the Discrete Wavelet Transform
Kunal Mukherjee, Amar Mukherjee
Abstract:
We present a new wavelet transform algorithm with a data flow that can fully exploit the locality property of wavelets. This leads to highly optimized fine grained wavelet coding algorithms, in terms of pipelinging performance,flexible data granularity and reliablity of transmission. It can be used by all wavelet coding methods, and hass been demonstrated to improve the performance of the most successful ones. We propse a new bottom-up Embedded Zerotree Wavelet(EZW) image coding algorithm, and demonstrate a 5-10% speedup over EZW, by means of close coupling between the new wavelet transform algorithm and EZW encoding....
RMF based Adaptive Block-wise Compression
Tao Tao, Amar Mukherjee
Abstract:
In this paper, we present a new RMF(Recursive Merge Filter) based adaptive block-wise compression method. We propose this method based on two works, one is the FWT(fast Wavelet transform) based adaptive block-wise compression method and the other one is a new DWT (discrete wavelet transform) algorithm called RMF algorithm. The FWT based adaptive block-wise compression method[] has the limitation that it is not possible to do sub-image level encoding necessary for progressive encoding. The RMF algorithm, which has the same computation result as FWT but has different data flow, has the advantage that it maintains the spatial locality property of wavelet coefficients which are computed in a bottom up fashion...
RMF Based EZW Image Compression Method
Tao Tao, Kunal Mukherjee, Amar Mukherjee
Abstract:
In this paper, we present a new RMF(Recursive Merge Filter) based EZW (Embedded Image Coding Using Zero-trees of Wavelet coefficients) image compression method. We propose this method based on two works, one is the EZW algorithm and the other one is a new DWT(Discrete Wavelet Transform) algorithm called RMF algorithm. The EZW algorithm, which is a veru successful wavelet based image compression method, has two main limitations - the sub-image level encoding is not possible and the computational complexity is high. The RMF algorithm, which has the same computation result as FWT(Fast Wavelet Transform) but has a different data flow, has the advantage that it maintains the spatail locality property of wavelet coefficients which are computed in a bottom up fashion...

Lossless,Reversible Transformation that improve Text compression Ratios
Robert Franceschini, Holger Kruse, Nan Zhang, Raja Iqbal, Amar Mukherjee
Abstract:
Lossless Compression researchers have developed highly sophisticate approaches such as huffman coding, airthmetic encoding, the Lempel-Ziv family, Dynamic Markov Compression(DMC), Prediciton by Partial Matching(PPM), and Burrow-Wheeler Transform(BWT) based algorithms. However none of these methods has been able to reach the theoretical best case compression ratio consistely, which suggest that better algorithms may be possible. Once approach for trying to attain better compression ratio is to develop different compression algorithm. As alternative approach, however, is to develop generic, reversible transformations that can be applied to a source text that improve an exisiting, or backend, algorithm's ability to compress. This paper explores the latter strategy...

Novel Hardware-Software Architecture for the Recursive Merge Filtering Algorithm.
Piyush Jamkhandi, Amar Mukherjee Kunal Mukherjee, Robert Franceschini
Abstract:
As reconfigurable devices move to the forefront of mainstream processing, the spectrum of application areas for such devices is also increasing. One such area is image processing. In this paper we present a novel hardware-software codesign architecture for computation of the Discrete Wavelet Tranform(DWT), based on a new recursive Merge Filtering (RMF) algorithm. The architecture aims at reducing the overall data routing during computation of the DWT. The method shows how data routing can be transofrmed into a series of index computation carried out on reconfigurable device.
Download PowerPoint Presentation cancun.ppt (1488384)