05780474

a

05780474 Greve, Mark J{\o}rgensen, Allan Gr{\o}nlund Larsen, Kasper Dalgaard Truelsen, Jakob Cell probe lower bounds and approximations for range mode. Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6--10, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-14164-5/pbk). Lecture Notes in Computer Science 6198, 605-616 (2010). 2010 Berlin: Springer EN

doi:10.1007/978-3-642-14165-2_51

Summary: The mode of a multiset of labels, is a label that occurs at least as often as any other label. The input to the range mode problem is an array $A$ of size $n$. A range query $[i,j]$ must return the mode of the subarray $A[i],A[i + 1],\dots ,A[j]$. We prove that any data structure that uses $S$ memory cells of $w$ bits needs $\Omega(\frac{{\log} n}{\log (Sw/n)})$ time to answer a range mode query. Secondly, we consider the related range $k$-frequency problem. The input to this problem is an array $A$ of size $n$, and a query $[i,j]$ must return whether there exists a label that occurs precisely $k$ times in the subarray $A[i],A[i + 1],\dots ,A[j]$. We show that for any constant $k > 1$, this problem is equivalent to 2D orthogonal rectangle stabbing, and that for $k = 1$ this is no harder than four-sided 3D orthogonal range emptiness. Finally, we consider approximate range mode queries. A $c$-approximate range mode query must return a label that occurs at least $1/c$ times that of the mode. We describe a linear space data structure that supports 3-approximate range mode queries in constant time, and a data structure that uses $O(\frac{n}{\varepsilon})$ space and supports $(1 + \epsilon )$-approximation queries in $O({\log} {\frac {1}{\varepsilon}})$ time.