PUMA
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.
 
 
Abstract
(English)
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
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