Aarhus University Seal / Aarhus Universitets segl

Bryan T. Wilkinson

Linear-Space Data Structures for Range Mode Query in Arrays

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Timothy M. Chan
  • ,
  • Stephane Durocher
  • ,
  • Kasper Green Larsen
  • ,
  • Jason Morrison
  • ,
  • Bryan T. Wilkinson
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 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(sqrt(n) loglog n) query time. We improve their result and present an O(n)-space data structure that supports range mode queries in O(sqrt(n / log n)) worst-case time. Furthermore, we present strong evidence that a query time significantly below sqrt(n) cannot be achieved by purely combinatorial techniques; we show that boolean matrix multiplication of two sqrt(n) by sqrt(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(n^(1-1/d^2)) time).
Original languageEnglish
JournalLeibniz International Proceedings in Informatics
Volume14
Pages (from-to)290-301
Number of pages11
ISSN1868-8969
DOIs
Publication statusPublished - 2012
Externally publishedYes
EventSymposium on Theoretical Aspects of Computer Science - Paris, France
Duration: 1 Mar 20123 Mar 2012

Conference

ConferenceSymposium on Theoretical Aspects of Computer Science
CountryFrance
CityParis
Period01/03/201203/03/2012

Bibliographical note

Title of the vol.: 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France / ed. by Christoph Dürr, Thomas Wilke.
ISBN 978-3-939897-35-4

See relations at Aarhus University Citationformats

ID: 52616395