Abstract. 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 . We prove that any data structure that uses S memory cells of w bits needs Ω( 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 . 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( n ε ) space and supports (1 + ε)-approximation queries in O(log 1 ε ) time.
Greve et al. REF prove a lower bound of Ω( lg n lg( sw n ) ) query time for any range mode query data structure that uses s memory cells of w bits.
Cell probe lower bounds and approximations for range mode
In Proc. 37th International Colloquium on Automata, Languages, and Programming
Mathematics Computer Science