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.