Optimal Encodings for Range Majority Queries

Abstract

We study the problem of designing a data structure that reports the positions of the distinct $\tau$-majorities within any range of an array $A[1,n]$, without storing $A$. A $\tau$-majority in a range $A[i,j]$, for $0<\tau <1$, is an element that occurs more than $\tau (j-i+1)$ times in $A[i,j]$. We show that $\Omega (n\log (1/\tau ))$ bits are necessary for any data structure able just to count the number of distinct $\tau$-majorities in any range. Then, we design a structure using $O(n\log (1/\tau ))$ bits that returns one position of each $\tau$-majority of $A[i,j]$ in $O((1/\tau )\log {\log }_w(1/\tau )\log n)$ time, on a RAM machine with word size $w$ (it can output any further position where each $\tau$-majority occurs in $O(1)$ additional time). Finally, we show how to remove a $\log n$ factor from the time by adding $O(n\log \log n)$ bits of space to the structure.

References in corpus (1)

• Time-Space Trade-Offs for Predecessor Search