We study the problem of designing a data structure that reports the positions of the distinct @math -majorities within any range of an array @math , without storing @math . A @math -majority in a range @math , for @math , is an element that occurs more than @math times in @math . We show that @math bits are necessary for any data structure able just to count the number of distinct @math -majorities in any range. Then, we design a structure using @math bits that returns one position of each @math -majority of @math in @math time, on a RAM machine with word size @math (it can output any further position where each @math -majority occurs in @math additional time). Finally, we show how to remove a @math factor from the time by adding @math bits of space to the structure.
Range @math -majority queries were introduced by Karpinski and Nekrich @cite_19 , who presented an @math -words structure with @math query time. @cite_0 improved their word-space and query time to @math and @math , respectively. @cite_3 presented another trade-off, where the space is @math bits and the query time is @math . Here @math denotes the empirical entropy of the distribution of elements in @math (we use @math to denote the logarithm in base 2). The best current result in general is by @cite_9 , where the space is @math words and the query time is @math . All these results assume that @math is fixed at construction time.
@cite_0 @cite_19 @cite_9 @cite_3
2156839950 2951951354 2949155877 6548167
Given an array A of size n, we consider the problem of answering range majority queries: given a query range [i..j] where 1= We study a new variant of colored orthogonal range searching problem: given a query rectangle @math all colors @math , such that at least a fraction @math of all points in @math are of color @math , must be reported. We describe several data structures for that problem that use pseudo-linear space and answer queries in poly-logarithmic time. 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. We show how to store a compressed two-dimensional array such that, if we are asked for the elements with high relative frequency in a range, we can quickly return a short list of candidates that includes them. More specifically, given an m × n array A and a fraction α > 0, we can store A in O(mn(H + 1)log2(1 α) bits, where H is the entropy of the elements' distribution in A, such that later, given a rectangular range in A and a fraction β ≥ α, in O(1 β) time we can return a list of O(1 β) distinct array elements that includes all the elements that have relative frequency at least β in that range. We do not verify that the elements in the list have relative frequency at least β, so the list may contain false positives. In the case when m = 1, i.e., A is a string, we improve this space bound by a factor of log(1 α), and explore a spacetime trade off for verifying the frequency of the elements in the list. This leads to an O(n min(log(1 α), H +1) log n) bit data structure for strings that, in O(1 β) time, can return the O(1 β) elements that have relative frequency at least β in a given range, without false positives, for β ≥ α.