PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Ferragina P., Sėren J., Venturini R. Distribution-aware compressed full-text indexes. In: Algorithmica, vol. 67 (4) pp. 529 - 546. Springer, 2013.
 
 
Abstract
(English)
In this paper we address the problem of building a compressed self-index that, given a distribution for the pattern queries and a bound on the space occupancy, minimizes the expected query time within that index space bound. We solve this problem by exploiting a reduction to the problem of finding a minimum weight $K$-link path in a properly designed Directed Acyclic Graph. Interestingly enough, our solution can be used with any compressed index based on the Burrows-Wheeler transform. Our experiments compare this optimal strategy with several other known approaches, showing its effectiveness in practice.
URL: http://link.springer.com/article/10.1007/s00453-013-9782-3
DOI: 10.1007/s00453-013-9782-3
Subject Indexing
H.3 INFORMATION STORAGE AND RETRIEVAL


Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional