Linear-space data structures for range mode query in arrays

A mode of a multiset S is an element a ∈ S of maximum multiplicity; that is, a occurs at least as frequently as any other element in S. Given an array A[1: n] of n elements, we consider a basic problem: constructing a static data structure that efficiently answers range mode queries on A. Each query consists of an input pair of indices (i, j) for which a mode of A[i: j] must be returned. The best previous data structure with linear space, by Krizanc, Morin, and Smid (ISAAC 2003), requires Θ( n log logn) query time in the worst case. We improve their result and present an O(n)-space data structure that supports range mode queries in O( n / logn) worst-case time. In the external memory model, we give a linear-space data structure that requires O( n/B) I/Os per query, where B denotes the block size. Furthermore, we present strong evidence that a query time significantly below n cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two n×√n matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for the dynamic problem (queries and updates in near O(n3/4) time), for orthogonal range mode in d dimensions (queries in near O(n1−1/2d) time) and for half-space range mode in d dimensions (queries in O(n1−1/d 2) time). Finally, we complement our dynamic data structure with a reduction from the multiphase problem, again supporting that we cannot hope for much more efficient data structures.