Towards Optimal Range Medians

DOI10.1007/978-3-642-02927-1_40MaRDI QIDQ3638057zbMATH OpenOpenAlexFDO

Authors Beat Gfeller, Peter Sanders

Publication date 14 July 2009

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0901.1761

Mathematics Subject Classification ID

Searching and sorting (68P10)

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 uses O(n) space and needs $O(nlogk+klogn)$ time to answer the first $k$ queries. This improves previous algorithms by a logarithmic factor and matches a lower bound for $k=O(n)$. Since the algorithm decomposes the range of element values rather than the array, it has natural generalizations to higher dimensional problems -- it reduces a range median query to a logarithmic number of range counting queries.

Recommendations

• Towards optimal range medians
• Range Medians
• Data structures for range median queries
• Improved Bounds for Range Mode and Range Median Queries
• Range selection and median: tight cell probe lower bounds and adaptive data structures

Cited in

(12)

• Linear-space data structures for range mode query in arrays
• The optimal statistical median of a convex set of arrays
• Range selection and predecessor queries in data aware space and time
• Linear-space data structures for range frequency queries on arrays and trees
• The reverse problem of range query
• Array range queries
• Range Medians
• Data structures for range median queries
• New algorithms on wavelet trees and applications to information retrieval
• Range selection and median: tight cell probe lower bounds and adaptive data structures
• Towards optimal range medians
• Maximizing the optimality streak of deferred data structuring (a.k.a. database cracking)

This page was built for publication: Towards Optimal Range Medians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638057)