Istituto di Scienza e Tecnologie dell'Informazione     
Ferragina P., Sirén J., Venturini R. Distribution-aware compressed full-text indexes. In: ESA 2011 - Algorithms – ESA 2011. 19th Annual European Symposium (Saarbrucken, Germany, 5-9 September 2011). Proceedings, pp. 760 - 771. Camil Demetrescu, Magnús M. Halldórsson (eds.). (Lecture Notes in Computer Science, vol. 6942). Springer, 2011.
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 particular Directed Acyclic Graph. Interestingly enough, our solution is independent of the underlying compressed index in use. Our experiments compare this optimal strategy with several other standard approaches, showing its effectiveness in practice.
URL: http://www.springerlink.com/content/680774608r741802/
DOI: 10.1007/978-3-642-23719-5_64
Subject Compression
F.2.2 Nonnumerical Algorithms and Problems Pattern Matching

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