Jason Morrison

  1. Linear-Space Data Structures for Range Mode Query in Arrays.

    Authors: Stephane Durocher, Jason Morrison
    Subjects: Data Structures and Algorithms
    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 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^{2-2\epsilon})$-space static data structure
    that supports range mode queries in $O(n^\epsilon)$ time in the worst case, for
    any fixed $\epsilon \in [0,1/2]$.

Syndicate content