Linear-Space Data Structures for Range Mode Query in Arrays

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

Research output: Contribution to journalArticlepeer-review

Abstract

A mode of a multiset S is an element a∈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 (Proceedings of the International Symposium on Algorithms and Computation (ISAAC), pp. 517–526, 2003), requires (Formula Presented.) query time in the worst case. We improve their result and present an O(n)-space data structure that supports range mode queries in (Formula Presented.) worst-case time. In the external memory model, we give a linear-space data structure that requires (Formula Presented.) I/Os per query, where B denotes the block size. Furthermore, we present strong evidence that a query time significantly below (Formula Presented.) cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two (Formula Presented.) 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(n3/4) time), for orthogonal range mode in d dimensions (queries in near O(n1−1/2d) time) and for half-space range mode in d dimensions (queries in (Formula Presented.) 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.

Original languageEnglish (US)
Pages (from-to)719-741
Number of pages23
JournalTheory of Computing Systems
Volume55
Issue number4
DOIs
StatePublished - Nov 2014
Externally publishedYes

Keywords

  • Array
  • Data structure
  • Linear space
  • Mode
  • Range query

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Linear-Space Data Structures for Range Mode Query in Arrays'. Together they form a unique fingerprint.

Cite this