Document - Distribution-aware compressed full-text indexes

2013

Journal article Open Access

Distribution-aware compressed full-text indexes

Ferragina P, Sì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, vol. 67 (issue 4), pp. 529-546

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 Sìren J and Venturini R},
	doi = {10.1007/s00453-013-9782-3 and 10.1007/978-3-642-23719-5_64},
	year = {2013}
}