DIMACS Working Group on The Burrows - Wheeler Transform: Ten Years Later

August 19 - 20, 2004
DIMACS Center, CoRE Building, Rutgers University, Piscataway, NJ

Organizers:

Paolo Ferragina, University of Pisa

Giovanni Manzini, University of Piemonte Orientale

S. Muthukrishnan, Rutgers University, muthu@cs.rutgers.edu

Workshop Program:

Thursday, August 19, 2004

 8:15 -  8:50 Breakfast and registration - CoRE Building, 4th Floor

 8:50 -  9:00 Welcome and opening remarks 
              S. Muthukrishnan, DIMACS and Rutgers University

 9:00 - 10:00 The pre-history and future of the block-sorting compression algorithm 
              Mike Burrows, Google

10:00 - 10:30 Break

10:30 - 11:00 An Error-Resilient Blocksorting Compression Algorithm
              Nasir Memon, Polytechnic University, USA
              (Joint with Lee Butterman, Brown University, USA)

11:00 - 11:30 Compression Boosting Using the Burrows-Wheeler Transform
              Giovanni Manzini, University Piemonte Orientale, Italy
              (Joint with Paolo Ferragina, University of Pisa, Italy, 
              Raffaele Giancarlo, University of Palermo, Italy, 
              Marinella Sciortino, University of Palermo, Italy)

11:30 - 12:00 Using the Burrows Wheeler Transform for PPM
              compression without escapes
              Peter Fenwick, Auckland University, NZ

12:00 - 12:30 Generalized Burrows-Wheeler Transform 
              Marinella Sciortino, University of Palermo, Italy
              (Joint with Sabrina Mantaci, Antonio Restivo, University of Palermo, Italy)

12:30 -  2:30 Lunch

 2:30 -  3:00 A survey of suffix sorting
              Martin Farach-Colton, Rutgers University, USA

 3:00 -  3:30 Fast BWT in Small Space by Blockwise Suffix Sorting
              Juha Karkkainen, University of Finland

 3:30 -  4:00 Efficient computation of the Burrows-Wheeler Transform
              Kunihiko Sadakane, Kyushu University, Japan

 4:00 -  4:30 Break

 4:30 -  5:00 The FM-index: A compressed full-text index based on the BWT
              Paolo Ferragina, University of Pisa, Italy 
              (Joint with Giovanni Manzini, University of Piemonte Orientale, Italy)

 5:00 -  5:30 Run-length FM-index 
              Veli Makinen, University of Helsinki, Finland
              (Joint with Gonzalo Navarro, University of Chile)

 5:30 -  6:00 Entropy-Compressed Indexes for Multidimensional Pattern Matching
              Ankur Gupta, Duke University, USA
              (Joint with Roberto Grossi, University of Pisa, Italy, 
              Jeff Vitter, Purdue University, USA) 

 7:00         Dinner at Makeda Restaurant

Friday, August 20, 2004

 8:45 -  9:30 Breakfast and registration

 9:30 - 10:00 Remote file and data synchronization: State-of-the-art and open problems 
              Torsten Suel, Polytechnic University, USA

10:00 - 10:30 Toward Ubiquitous Compression
              Fred Douglis, IBM T.J. Watson, USA

10:30 - 11:00 Break

11:00 - 11:30 Vcodex: A Platform of Data Transformers
              Kiem-Phong Vo, AT&T Labs Research, USA

11:30 - 12:00 Block Sorting Lossless Delta Compression Algorithms
              James J. Hunt, Fzi, Germany

12:00 - 12:30 Fast Gapped Variants of LZW compression 
              Alberto Apostolico, University of Padova, Italy

12:30 -  2:30 Lunch

 2:30 -  3:00 Comparing Sequences with Segment Rearrangements
              S. Cenk Sahinalp, Simon Fraser University, CA

 3:00 -  3:30 Grammar-based Compression of DNA Sequences
              Neva Cherniavsky, University of Washington, USA
              (Joint with Richard Ladner, University of Washington, USA)

 3:30 -  4:00 Break

 4:00 -  4:30 Compression of Words over a Partially Commutative Alphabet 
              Serap Savari, University of Michigan, USA

 4:30 -  5:00 Delayed-Dictionary Compression for Packet Networks
              Raanan Refua, Tel Aviv University, Israel
              (Joint with Yossi Matias, Tel Aviv University, Israel)

Previous: Participation

Workshop Index

DIMACS Homepage