Parallel and Distributed Compressed Indexes
Luís M. S. Russo, Gonzalo Navarro, Arlindo
L. Oliveira
Abstract:
We study parallel and distributed compressed indexes. Compressed indexes are
a new and functional way to index text strings. They exploit the
compressibility of the text, so that their size is a function of the
compressed text size. Moreover, they support a considerable amount
of functions, more than many classical indexes. We make use of this extended
functionality to obtain, in a shared-memory parallel machine, near-optimal
speedups for solving several stringology problems. We also show how to
distribute compressed indexes across several machines.
Luis Russo
2010-03-22