Luís M. S. Russo,

Inesc-ID –

Abstract:

A full-text index provides fast search for any pattern in a text.
Tradicional full-text indexes, however, have a serious problem with
space usage. A recent trend is to develop indexes that
exploit the compressibility of the text so that their size is a function
of the size of the compressed text.
This field has introduced the concept of self-indexes, which, in addition
to providing index capabilities, are capable of replacing the original text.
The two most successful lines of research are the ones exploring
compressed suffix arrays and the Burrows-Wheeler transform.
In this talk we will describe an algorithm that builds an index
based on the well known Ziv-Lempel data compression technique.
This algorithm represents a significant improvement over previous
methods. We expect that it will be very competitive against
the two mainstream approaches.

 

Date: 2006-Jan-06     Time: 14:30:00     Room: 336

For more information:

  • 213100228