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 O(√n log log n) query time. We improve their result and present an O(n)-space data structure that supports range mode queries in O(√n/logn) worst-case time. 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 orthogonal range mode in higher dimensions (queries in near O(n ^1-1/2d) time) and for halfspace range mode in higher dimensions (queries in O(n^1-1/d) time).