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.

Source: ESA 2013 - Algorithms. 21st Annual European Symposium, pp. 469–480, Sophia Antipolis, France, 2-4 September 2013

Metrics