Towards optimal range medians
From MaRDI portal
Publication:541663
DOI10.1016/J.TCS.2010.05.003zbMATH Open1220.68052OpenAlexW2571362173MaRDI QIDQ541663FDOQ541663
Authors: Beat Gfeller, Allan Grønlund Jørgensen, Gerth Stølting Brodal, Peter Sanders 
Publication date: 7 June 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.05.003
Recommendations
Cites Work
- Towards Optimal Range Medians
- Title not available (Why is that?)
- Range mode and range median queries in constant time and sub-quadratic space
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
- Design and implementation of an efficient priority queue
- Optimal External Memory Interval Management
- Title not available (Why is that?)
- Optimal bounds for the predecessor problem and related problems
- Title not available (Why is that?)
- Orthogonal range searching in linear and almost-linear space
- Fractional cascading. I: A data structuring technique
- An Online Algorithm for Finding the Longest Previous Factors
- Data structures for range median queries
- Range Medians
- On the Complexity of Maintaining Partial Sums
- Improved Bounds for Range Mode and Range Median Queries
- Title not available (Why is that?)
- Merging multiple lists on hierarchical-memory multiprocessors
- Deferred Data Structuring
- Title not available (Why is that?)
Cited In (21)
- Linear-space data structures for range frequency queries on arrays and trees
- Colored range queries and document retrieval
- Improved Bounds for Range Mode and Range Median Queries
- Data structures for range median queries
- Range mode and range median queries in constant time and sub-quadratic space
- New algorithms on wavelet trees and applications to information retrieval
- Array range queries
- Range selection and median: tight cell probe lower bounds and adaptive data structures
- Linear-space data structures for range mode query in arrays
- Compact binary relation representations with rich functionality
- The optimal statistical median of a convex set of arrays
- Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
- Dynamic path queries in linear space
- Range selection and predecessor queries in data aware space and time
- Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
- Linear-space data structures for range minority query in arrays
- Towards Optimal Range Medians
- Improved time and space bounds for dynamic range mode
- Range Medians
- Indexing for summary queries
- Optimal encodings for range top-\(k\), selection, and min-max
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 Q541663)
