Text Sparsification via Local Maxima

Pierluigi Crescenzi, Alberto Del Lungo, Roberto Grossi, Elena Lodi, Linda Pagli and Gianluca Rossi

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


In this paper, we investigate a text sparsification technique based on the identification of local maxima. In particular, we first show that looking for an order of the alphabet symbols that minimizes the number of local maxima in a given string is an NP-hard problem. Successively, we describe how the local maxima sparsification technique can be used to filter the access to unstructured texts. Finally, we experimentally show that this approach can be successfully used in order to create a space efficient index for searching a DNA sequence as quickly as a full index.

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Maintainer fsttcs20@cse.iitd.ernet.in.
Start Conference Manager
Conference Systems