Chan, Timothy M. ;
Durocher, Stephane ;
Larsen, Kasper Green ;
Morrison, Jason ;
Wilkinson, Bryan T.
LinearSpace Data Structures for Range Mode Query in Arrays
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 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)) worstcase 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 linearspace data structures for orthogonal range mode in higher dimensions (queries in near O(n^(11/2d)) time) and for halfspace range mode in higher dimensions (queries in O(n^(11/d^2)) time).
BibTeX  Entry
@InProceedings{chan_et_al:LIPIcs:2012:3425,
author = {Timothy M. Chan and Stephane Durocher and Kasper Green Larsen and Jason Morrison and Bryan T. Wilkinson},
title = {{LinearSpace Data Structures for Range Mode Query in Arrays}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {290301},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3425},
URN = {urn:nbn:de:0030drops34254},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2012.290},
annote = {Keywords: mode, range query, data structure, linear space, array}
}
Keywords: 

mode, range query, data structure, linear space, array 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Issue date: 

2012 
Date of publication: 

24.02.2012 