Compressed cache-oblivious string B-tree

Ferragina P, Venturini R

Indexing data structure  H.3 INFORMATION STORAGE AND RETRIEVAL  Data compression  Mathematics (miscellaneous)  Compressed index  Pattern matching  Indexing  String dictionary 

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.

Metrics