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 ) .
The first optimal-time and linear-space solution to document listing is due to Muthukrishnan @cite_2 , who solves the problem in @math time using an index of @math bits of space. Later solutions @cite_21 @cite_42 improved the space to essentially the statistical entropy of @math , at the price of multiplying the times by low-order polylogs of @math (e.g., @math time with @math bits on top of the entropy @cite_21 @cite_26 ). However, statistical entropy does not capture repetitiveness well @cite_49 , and thus these solutions are not satisfactory in repetitive collections.
@cite_26 @cite_21 @cite_42 @cite_49 @cite_2
2949155877 2620416450 2107082304 2508919161
Karpinski and Nekrich (2008) introduced the problem of parameterized range majority, which asks to preprocess a string of length @math such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold @math . Subsequent authors have reduced their time and space bounds such that, when @math is given at preprocessing time, we need either @math space and optimal @math query time or linear space and @math query time, where @math is the alphabet size. In this paper we give the first linear-space solution with optimal @math query time. For the case when @math is given at query time, we significantly improve previous bounds, achieving either @math space and optimal @math query time or compressed space and @math query time. Along the way, we consider the complementary problem of parameterized range minority that was recently introduced by (2012), who achieved linear space and @math query time even for variable @math . We improve their solution to use either nearly optimally compressed space with no slowdown, or optimally compressed space with nearly no slowdown. Some of our intermediate results, such as density-sensitive query time for one-dimensional range counting, may be of independent interest. Indexing highly repetitive texts --- such as genomic databases, software repositories and versioned text collections --- has become an important problem since the turn of the millennium. A relevant compressibility measure for repetitive texts is @math , the number of runs in their Burrows-Wheeler Transform (BWT). One of the earliest indexes for repetitive collections, the Run-Length FM-index, used @math space and was able to efficiently count the number of occurrences of a pattern of length @math in the text (in loglogarithmic time per pattern symbol, with current techniques). However, it was unable to locate the positions of those occurrences efficiently within a space bounded in terms of @math . Since then, a number of other indexes with space bounded by other measures of repetitiveness --- the number of phrases in the Lempel-Ziv parse, the size of the smallest grammar generating the text, the size of the smallest automaton recognizing the text factors --- have been proposed for efficiently locating, but not directly counting, the occurrences of a pattern. In this paper we close this long-standing problem, showing how to extend the Run-Length FM-index so that it can locate the @math occurrences efficiently within @math space (in loglogarithmic time each), and reaching optimal time @math within @math space, on a RAM machine of @math bits. Within @math space, our index can also count in optimal time @math . Raising the space to @math , we support count and locate in @math and @math time, which is optimal in the packed setting and had not been obtained before in compressed space. We also describe a structure using @math space that replaces the text and extracts any text substring of length @math in almost-optimal time @math . (...continues...) Given a sequence S e s1s2…sn of integers smaller than r e O(polylog(n)), we show how S can be represented using nH0(S) p o(n) bits, so that we can know any sq, as well as answer rank and select queries on S, in constant time. H0(S) is the zero-order empirical entropy of S and nH0(S) provides an information-theoretic lower bound to the bit storage of any sequence S via a fixed encoding of its symbols. This extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in O(log r) time. For larger r, we can still represent S in nH0(S) p o(n log r) bits and answer queries in O(log r log log n) time. Another contribution of this article is to show how to combine our compressed representation of integer sequences with a compression boosting technique to design compressed full-text indexes that scale well with the size of the input alphabet Σ. Specifically, we design a variant of the FM-index that indexes a string T[1, n] within nHk(T) p o(n) bits of storage, where Hk(T) is the kth-order empirical entropy of T. This space bound holds simultaneously for all k ≤ α logvΣv n, constant 0 Compared to all previous works, our index is the first that removes the alphabet-size dependance from all query times, in particular, counting time is linear in the pattern length. Still, our index uses essentially the same space of the kth-order entropy of the text T, which is the best space obtained in previous work. We can also handle larger alphabets of size vΣv e O(nβ), for any 0 [See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the @math -Approximate Near Neighbor Search problem. For the @math -dimensional Euclidean space and @math -point datasets, we develop a data structure with space @math and query time @math for every @math such that: This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor @math , improving upon [Kapralov, PODS 2015]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [Becker, Ducas, Gama, Laarhoven, SODA 2016] and data-dependent hashing [Andoni, Indyk, Nguyen, Razenshteyn, SODA 2014] [Andoni, Razenshteyn, STOC 2015]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole above trade-off in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match the above trade-off for @math , improving upon the best known lower bounds from [Panigrahy, Talwar, Wieder, FOCS 2010]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes.