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 et al. 2006) the ability to decompress prefixes of the stored strings I/O-optimally still preserving its space bounds.

### Compressed Cache-Oblivious String B-tree

#### Abstract

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 et al. 2006) the ability to decompress prefixes of the stored strings I/O-optimally still preserving its space bounds.
##### Scheda breve Scheda completa Scheda completa (DC)
9783642404498
9783642404504
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11568/245368
• ND
• 5
• 3