Towards optimal range medians

DOI10.1016/j.tcs.2010.05.003zbMath1220.68052OpenAlexW2571362173MaRDI QIDQ541663

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

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

zbMATH Keywords

algorithmsdata structuresmediansrange queries

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05)

Related Items

Optimal Encodings for Range Top-$$k$$, Selection, and Min-Max, Range selection and predecessor queries in data aware space and time, Indexing for summary queries, Compact binary relation representations with rich functionality, Colored range queries and document retrieval, New algorithms on wavelet trees and applications to information retrieval, Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds, Linear-space data structures for range minority query in arrays, Improved Time and Space Bounds for Dynamic Range Mode, Linear-space data structures for range mode query in arrays, Spaces, Trees, and Colors, Dynamic path queries in linear space, Array Range Queries, Linear-space data structures for range frequency queries on arrays and trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Range mode and range median queries in constant time and sub-quadratic space
• Orthogonal range searching in linear and almost-linear space
• Fractional cascading. I: A data structuring technique
• Merging multiple lists on hierarchical-memory multiprocessors
• Optimal bounds for the predecessor problem and related problems
• Range Medians
• An Online Algorithm for Finding the Longest Previous Factors
• Towards Optimal Range Medians
• Data Structures for Range Median Queries
• On the Complexity of Maintaining Partial Sums
• Deferred Data Structuring
• Design and implementation of an efficient priority queue
• Optimal External Memory Interval Management
• Improved Bounds for Range Mode and Range Median Queries
• Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting