Better Space Bounds for Parameterized Range Majority and Minority
Djamal Belazzougui, Travis Gagie, and Gonzalo Navarro
Karpinski and Nekrich (2008) introduced the problem of parameterized range
majority, which asks to preprocess a string of length n 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
t.
Subsequent authors have reduced their time and space bounds such that, when
t is given at preprocessing time, we need either O(n log(1/t))
space and optimal O(1/t) query time or linear space and O((1/t)
log log s) query time, where s is the alphabet size. In
this paper we give the first linear-space solution with optimal O(1/t)
query time. For the case when t is given at query time, we
significantly improve previous bounds, achieving either O(n log log s)
space and optimal O(1/t) query time or compressed space and
O((1/t) log (log(1/t)/log log n)) query time. Along
the way, we consider the complementary problem of parameterized range minority
that was recently introduced by Chan et al. (2012), who achieved linear space
and O(1/t) query time even for variable t. 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.