Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson

View Abstract
A mode of a multiset S is an element a in 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 Theta(sqrt{n} loglog n) 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(sqrt{n/log n}) worst-case time. In the external memory model, we give a linear-space data structure that requires O(sqrt{n/B}) I/Os per query, where B denotes the block size. Furthermore, we present strong evidence that a query time significantly below sqrt(n) cannot be achieved by purely *combinatorial* techniques; we show that boolean matrix multiplication of two sqrt(n) x sqrt(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(n^{3/4}) time), for orthogonal range mode in d dimensions (queries in near O(n^{1-1/2d}) time) and for half-space range mode in d dimensions (queries in O(n^{1-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.

**STACS’12:** 29th Symposium on Theoretical Aspects of Computer Science

**ToCS:** Theory of Computing Systems (STACS’12 special issue)