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 ) .
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.
@cite_39
2103465290
This paper compares different indexing techniques proposed for supporting efficient access to temporal data. The comparison is based on a collection of important performance criteria, including the space consumed, update processing, and query time for representative queries. The comparison is based on worst-case analysis, hence no assumptions on data distribution or query frequencies are made. When a number of methods have the same asymptotic worst-case behavior, features in the methods that affect average case behavior are discussed. Additional criteria examined are the pagination of an index, the ability to cluster related data together, and the ability to efficiently separate old from current data (so that larger archival storage media such as write-once optical disks can be used). The purpose of the paper is to identify the difficult problems in accessing temporal data and describe how the different methods aim to solve them. A general lower bound for answering basic temporal queries is also introduced.