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.
My Menu
Saved Items

Text Sparsification via Local Maxima
Extended Abstract

Pilu CrescenziContact Information, Alberto Del LungoContact Information, Roberto GrossiContact Information, Elena LodiContact Information, Linda PagliContact Information and Gianluca RossiContact Information

(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”.

Contact Information Pilu Crescenzi
Email: piluc@dsi.unifi.it

Contact Information Alberto Del Lungo
Email: dellungo@unisi.it

Contact Information Roberto Grossi
Email: grossi@di.unipi.it

Contact Information Elena Lodi
Email: lodi@unisi.it

Contact Information Linda Pagli
Email: pagli@di.unipi.it

Contact Information Gianluca Rossi
Email: rossig@dsi.unifi.it
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.108 • Server: mpweb08
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)