Stephane Durocher
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 a list A[1:n] of n items, we consider the problem of constructing a 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. Building on work of Krizanc, Morin, and Smid (ISAAC 2003), we present an O(n)-space static data structure that supports range mode queries in O(sqrt(n/log n)) time in the worst case. This is the first linear-space data structure to guarantee o(sqrt(n)) query time. This is joint work with Timothy Chan, Kasper Larsen, Jason Morrison, and Bryan Wilkinson.