Towards Optimal Range Median

Gerth Stølting Brodal, Beat Gfeller, Allan Grønlund Jørgensen, and Peter Sanders

In Theoretical Computer Science, Special issue of ICALP'09, volume 412(24), pages 2588-2601, 2011.

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(nlog k + klog n) 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(nlog n) 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(nlog n) time where the time per query is reduced to O(log n / log log n). We also give efficient dynamic variants of both data structures, achieving O(log2 n) query time using O(nlog n) space in the comparison model and O((log n/loglog n)2) query time using O(nlog n/log log n) 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 Ω(log n/loglog n) 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.

Copyright notice

Copyright © 2010 by Elsevier Inc.. All rights reserved.

DOI

10.1016/j.tcs.2010.05.003

BIBTEX entry

@article{tcs11,
  author = "Gerth Stølting Brodal and Beat Gfeller and Allan Grønlund Jørgensen and Peter Sanders",
  doi = "10.1016/j.tcs.2010.05.003",
  issn = "0304-3975",
  journal = "Theoretical Computer Science, Special issue of ICALP'09",
  number = "24",
  pages = "2588-2601",
  publisher = "Elsevier Science",
  title = "Towards Optimal Range Median",
  volume = "412",
  year = "2011"
}

Other versions