TY - JOUR

T1 - Linear-Space Data Structures for Range Mode Query in Arrays

AU - Chan, Timothy M.

AU - Durocher, Stephane

AU - Larsen, Kasper Green

AU - Morrison, Jason

AU - Wilkinson, Bryan T.

N1 - Funding Information:
A preliminary version of these results appeared at the 29th Symposium on Theoretical Aspects of Computer Science (STACS) [15]. Work was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC), and in part by MADALGO—Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation.

PY - 2014/11

Y1 - 2014/11

N2 - 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.

AB - 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.

KW - Array

KW - Data structure

KW - Linear space

KW - Mode

KW - Range query

UR - http://www.scopus.com/inward/record.url?scp=84874592191&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84874592191&partnerID=8YFLogxK

U2 - 10.1007/s00224-013-9455-2

DO - 10.1007/s00224-013-9455-2

M3 - Article

AN - SCOPUS:84874592191

VL - 55

SP - 719

EP - 741

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 4

ER -