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: Chapter in Book/Report/Conference proceedingConference contribution

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 (ISAAC 2003), requires O(√n log log n) query time. We improve their result and present an O(n)-space data structure that supports range mode queries in O(√n/logn) worst-case time. Furthermore, we present strong evidence that a query time significantly below √n cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two √n × √n matrices reduces to n range mode queries in an array of size O(n). Additionally, we give linear-space data structures for orthogonal range mode in higher dimensions (queries in near O(n 1-1/2d) time) and for halfspace range mode in higher dimensions (queries in O(n1-1/d) time).

Original languageEnglish (US)
Title of host publication29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012
Pages290-301
Number of pages12
DOIs
StatePublished - Dec 1 2012
Externally publishedYes
Event29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012 - Paris, France
Duration: Feb 29 2012Mar 3 2012

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume14
ISSN (Print)1868-8969

Other

Other29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012
CountryFrance
CityParis
Period2/29/123/3/12

Keywords

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

ASJC Scopus subject areas

  • Software

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