Better space bounds for parameterized range majority and minority

DOI10.1007/978-3-642-40104-6_11MaRDI QIDQ2842150zbMATH OpenOpenAlexFDO

Authors Djamal Belazzougui, Travis Gagie, Gonzalo Navarro

Publication date 12 August 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.1765

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Algorithms on strings (68W32)

Abstract: 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 $au$. Subsequent authors have reduced their time and space bounds such that, when $au$ is given at preprocessing time, we need either $Ohnlog(1/au)$ space and optimal $Oh1/au$ query time or linear space and $Oh(1/au)loglogsigma$ query time, where $sigma$ is the alphabet size. In this paper we give the first linear-space solution with optimal $Oh1/au$ query time. For the case when $au$ is given at query time, we significantly improve previous bounds, achieving either $Ohnloglogsigma$ space and optimal $Oh1/au$ query time or compressed space and $Oh(1/au)logfraclog(1/au)logw$ 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 $Oh1/au$ query time even for variable $au$. 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.

Recommendations

• Range majorities and minorities in arrays
• Compressed dynamic range majority and minority data structures
• Optimal encodings for range majority queries
• Optimal query time for encoding range majority
• Range Majority in Constant Time and Linear Space

Cited in

(11)

• Range majorities and minorities in arrays
• Compressed dynamic range majority and minority data structures
• Optimal query time for encoding range majority
• Linear-space data structures for range frequency queries on arrays and trees
• Optimal encodings for range majority queries
• Array range queries
• Range Majority in Constant Time and Linear Space
• Dynamic range majority data structures
• Tree path majority data structures
• Fast identification of heavy hitters by cached and packed group testing
• Tree path majority data structures

This page was built for publication: Better space bounds for parameterized range majority and minority

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842150)