Speaker: Stephane Durocher
Title: Linear-Space Data Structures for Range Mode Query in Arrays

Abstract:
A mode of a multiset S is an element x in S of maximum multiplicity;
that is, x 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. We present an
O(n)-space static data structure that supports range mode queries in
O(min{sqrt(n), k, |j-i|+1}) time in the worst case, where k denotes
the number of distinct elements in A. This is the first linear-space
data structure to guarantee O(sqrt(n)) query time. Finally, we examine
generalizing our data structures to higher dimensions.

This work is joint with Jason Morrison.