On searching compressed string collections cache-obliviously

Current data structures for searching large string collec-tions are limited in that they either fail to achieve mini-mum space or they cause too many cache misses. In this paper, we discuss some edge linearizations of the classic trie data structure that are simultaneously cache-friendly and storable in compressed space. The widely-known front-coding scheme [26] is one example of linearization; it is at the core of Pre¯x B-trees and many other disk-conscious compressed indexes for string collections. However, it is largely thought of as a space-e®ective heuristic without ef-¯cient search support. In this paper, we introduce new insights on front-coding and other novel linearizations, and study how close their space occupancy is to the information-theoretic minimum. The moral is that they are not just heuristics. The second contribution of this paper engineers these linearizations to design a novel dictionary encoding scheme that achieves nearly optimal space, o®ers competitive I/O-search time, and is also conscious of the query distribution. Finally, we combine those data structures with cache-oblivious tries [6, 3] and obtain a succinct variant, whose space is close to the information-theoretic minimum. 1