Name
Abstract | ||
|---|---|---|
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 $\varTheta (\sqrt{n}\log\log n)$ query time in the worst case. 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. In the external memory model, we give a linear-space data structure that requires $O(\sqrt{n/B})$ I/Os per query, where B denotes the block size. 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} \times \sqrt{n}$ 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 ( n 3/4) time), for orthogonal range mode in d dimensions (queries in near O ( n 1 1/2 d ) time) and for half-space range mode in d dimensions (queries in $O(n^{1-1/d^{2}})$ 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00224-013-9455-2 | Theory of Computing Systems |
Keywords | DocType | Volume |
Mode,Range query,Data structure,Linear space,Array | Conference | 55 |
Issue | ISSN | Citations |
4 | 1432-4350 | 6 |
PageRank | References | Authors |
0.45 | 53 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Timothy M. Chan | 1 | 2033 | 150.55 |
| Stephane Durocher | 2 | 342 | 42.89 |
| Kasper Green Larsen | 3 | 355 | 29.32 |
| Jason Morrison | 4 | 137 | 9.81 |
| Bryan T. Wilkinson | 5 | 43 | 4.18 |