Towards optimal range medians |
| |
Authors: | Gerth Stølting Brodal Allan Grønlund Jørgensen |
| |
Affiliation: | a MADALGO11Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation., Department of Computer Science, Aarhus University, Denmarkb IBM Research, Zurich, Switzerlandc Universität Karlsruhe, Germany |
| |
Abstract: | We consider the following problem: Given an unsorted array of n elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which needs O(nlogk+klogn) time to answer k such median queries. This improves previous algorithms by a logarithmic factor and matches a comparison lower bound for k=O(n). The space complexity of our simple algorithm is O(nlogn) in the pointer machine model, and O(n) in the RAM model. In the latter model, a more involved O(n) space data structure can be constructed in O(nlogn) time where the time per query is reduced to O(logn/loglogn). We also give efficient dynamic variants of both data structures, achieving O(log2n) query time using O(nlogn) space in the comparison model and O((logn/loglogn)2) query time using O(nlogn/loglogn) space in the RAM model, and show that in the cell-probe model, any data structure which supports updates in O(logO(1)n) time must have Ω(logn/loglogn) query time.Our approach naturally generalizes to higher-dimensional range median problems, where element positions and query ranges are multidimensional—it reduces a range median query to a logarithmic number of range counting queries. |
| |
Keywords: | Medians Range queries Algorithms Data structures |
本文献已被 ScienceDirect 等数据库收录! |
|