Document - Distribution-aware compressed full-text indexes

2013

Journal article Open Access

Distribution-aware compressed full-text indexes

Ferragina P., Sìren J., Venturini R.

H.3 INFORMATION STORAGE AND RETRIEVAL Compression Computer Science Applications General Computer Science 113 Computer and information sciences Applied Mathematics Indexing

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.

Source: Algorithmica 67 (2013): 529–546. doi:10.1007/s00453-013-9782-3

Publisher: Springer Science + Business Media, New York , Stati Uniti d'America

Metrics

Back to previous page

Cite as

BibTeX entry

@article{oai:it.cnr:prodotti:277116,
	title = {Distribution-aware compressed full-text indexes},
	author = {Ferragina P. and Sìren J. and Venturini R.},
	publisher = {Springer Science + Business Media, New York , Stati Uniti d'America},
	doi = {10.1007/s00453-013-9782-3 and 10.1007/978-3-642-23719-5_64},
	journal = {Algorithmica},
	volume = {67},
	pages = {529–546},
	year = {2013}
}