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 -