Star Compression and Compressed Domain Pattern Matching

Prof. Amar Mukherjee

School of Electrical Engineering and Computer Science, Uni of Central Florida

Mon Dec 12 11:00:00 NZDT 2005 in Room 031, MSCS

Abstract

Data compression serves an obvious practical purpose: it conserves storage by removing redundancy, it enhances utilization of available bandwidth in a network and it also improves computer systems performance by reducing accesses to storage devices. Lossless text compression methods have been studied by researchers for the last half century and the techniques generally fall under three categories: statistical, dictionary based and transformation based. In the first half of the talk, I will present a relatively new transformation technique called Star transform which enables data compression with performance better than that of many existing compression algorithms. I will briefly present some of the variations of the theme of Star compression and their relative performances with respect to many classical and recent methods.

With increasing amount of text data being stored in compressed format, efficient information retrieval in the compressed domain has also become a major challenge. Being able to randomly access and partially decode the compressed data is highly desirable for efficient retrieval. In the second half of the talk, I will summarize our recent work on compressed domain pattern matching and information retrieval systems. Broadly, the compressed domain pattern matching and retrieval research has been based on BWT (Burrows-Wheeler Transform) and LZW (Ziv-Lempel-Welch) based compression methods. The two-pass compression approach for LZW algorithm can also be applied to lossless image compression.

The work reported in this talk is partially based on research jointly undertaken by Tim Bell of University of Canterbury, Christchurch, New Zealand; Donald Adjeroh of West Virginia University, USA; and the speaker; and is sponsored by funding from National Science Foundation (USA).