Abstract We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size N over alphabet [ 1 , σ ] is composed of D copies of a string of size n, and s edits are applied on ranges of copies. We introduce the first document listing index with size O ˜ ( n + s ) , precisely O ( ( n lg ⁡ σ + s lg 2 ⁡ N ) lg ⁡ D ) bits, and with useful worst-case time guarantees: Given a pattern of length m, the index reports the ndoc > 0 strings where it appears in time O ( m lg 1 + ϵ ⁡ N ⋅ ndoc ) , for any constant ϵ > 0 (and tells in time O ( m lg ⁡ N ) if ndoc = 0 ). Our technique is to augment a range data structure that is commonly used on grammar-based indexes, so that instead of retrieving all the pattern occurrences, it computes useful summaries on them. We show that the idea has independent interest: we introduce the first grammar-based index that, on a text T [ 1 , N ] with a grammar of size r, uses O ( r lg ⁡ N ) bits and counts the number of occurrences of a pattern P [ 1 , m ] in time O ( m 2 + m lg 2 + ϵ ⁡ r ) , for any constant ϵ > 0 . We also give the first index using O ( z lg ⁡ ( N z ) lg ⁡ N ) bits, where T is parsed by Lempel–Ziv into z phrases, counting occurrences in time O ( m lg 2 + ϵ ⁡ N ) .
@cite_39: Document retrieval aims at finding the most important documents where a pattern appears in a collection of strings. Traditional pattern-matching techniques yield brute-force document retrieval solutions, which has motivated the research on tailored indexes that offer near-optimal performance. However, an experimental study establishing which alternatives are actually better than brute force, and which perform best depending on the collection characteristics, has not been carried out. In this paper we address this shortcoming by exploring the relationship between the nature of the underlying collection and the performance of current methods. Via extensive experiments we show that established solutions are often beaten in practice by brute-force alternatives. We also design new methods that offer superior time space trade-offs, particularly on repetitive collections.
To be fair, those indexes perform well in many practical situations @cite_39 . However, in this article we are interested in whether providing worst-case guarantees in time and space.