Istituto di Scienza e Tecnologie dell'Informazione     
Ferragina P., Venturini R. Compressed cache-oblivious string B-tree. In: ESA 2013 - Algorithms. 21st Annual European Symposium (Sophia Antipolis, France, 2-4 September 2013). Proceedings, pp. 469 - 480. Hans L. Bodlaender, Giuseppe F. Italiano (eds.). (Lecture Notes in Computer Science, vol. 8125). Springer, 2013.
In this paper we address few variants of the well-known prefix-search problem in strings, and provide solutions for the cache-oblivious model which improve the best known results. In particular we close (asymptotically) the classic problem which asks for searching the set of strings sharing the longest common prefix with a queried pattern. Indeed, we provide an I/O-optimal solution matching the space lower bound for tries up to a constant multiplicative factor $(1+epsilon)$, for $epsilon>0$. Our solutions hinge upon few technicalities and, more interestingly, on a novel compressed storage scheme which adds to the elegant Locality Preserving Front-Coding (Bender {em et al.} 2006) the ability to decompress prefixes of the stored strings I/O-optimally still preserving its space bounds.
URL: http://link.springer.com/chapter/10.1007%2F978-3-642-40450-4_40
DOI: 10.1007/978-3-642-40450-4_40
Subject Indexing

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