Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Text Sparsification via Local Maxima
Extended Abstract
| |
|
Text Sparsification via Local Maxima
Extended Abstract
Pilu Crescenzi5 , Alberto Del Lungo6 , Roberto Grossi7 , Elena Lodi6 , Linda Pagli7 and Gianluca Rossi5 
| (5) |
Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, Via C. Lombroso 6/17, 50134 Firenze, Italy |
| (6) |
Dipartimento di Matematica, Università degli Studi di Siena, Via del Capitano 15, 53100 Siena, Italy |
| (7) |
Dipartimento di Informatica, Università degli Studi di Pisa, Corso Italia 40, 56125 Pisa, Italy |
Abstract
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.
Research partially supported by ITALIAN MURST project “Algoritmi per Grandi Insiemi di Dati: Scienza ed Ingegneria”.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|