Compressed Dynamic Range Majority and Minority Data Structures

Abstract

In the range $α$-majority query problem, we are given a sequence $S[1..n]$ and a fixed threshold $α\in (0, 1)$, and are asked to preprocess $S$ such that, given a query range $[i..j]$, we can efficiently report the symbols that occur more than $α(j-i+1)$ times in $S[i..j]$, which are called the range $α$-majorities. In this article we first describe a dynamic data structure that represents $S$ in compressed space --- $nH_k+ o(n\lg σ)$ bits for any $k = o(\log_σ n)$, where $σ$ is the alphabet size and $H_k \le H_0 \le \lgσ$ is the $k$-th order empirical entropy of $S$ --- and answers queries in $O \left(\frac{\log n}{α\log \log n} \right)$ time while supporting insertions and deletions in $S$ in $O \left( \frac{\lg n}α \right)$ amortized time. We then show how to modify our data structure to receive some $β\ge α$ at query time and report the range $β$-majorities in $O \left( \frac{\log n}{β\log \log n} \right)$ time, without increasing the asymptotic space or update-time bounds. The best previous dynamic solution has the same query and update times as ours, but it occupies $O(n)$ words and cannot take advantage of being given a larger threshold $β$ at query time. [ABSTRACT CLIPPED DUE TO LENGTH.]

Partially supported by Fondecyt grant 1-171058, Chile; NSERC, Canada; basal funds FB0001, Conicyt, Chile; and the Millenium Institute for Foundational Research on Data, Chile. A preliminary partial version of this article appeared in Proc. DCC 2017