Range mode and range median queries in constant time and sub-quadratic space

DOI10.1016/j.ipl.2008.10.007zbMath1191.68343OpenAlexW2090221650MaRDI QIDQ976080

Holger Petersen, Szymon Grabowski

Publication date: 16 June 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2008.10.007

zbMATH Keywords

algorithmscomputational complexitytheory of computation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Optimal encodings for range majority queries ⋮ Colored range queries and document retrieval ⋮ New algorithms on wavelet trees and applications to information retrieval ⋮ Linear-space data structures for range minority query in arrays ⋮ Range Majority in Constant Time and Linear Space ⋮ Enumerating Range Modes ⋮ Linear-space data structures for range mode query in arrays ⋮ Towards optimal range medians ⋮ Range majorities and minorities in arrays ⋮ Array Range Queries ⋮ Low space data structures for geometric range mode query

Cites Work

• Unnamed Item
• Fast Algorithms for Finding Nearest Common Ancestors
• Range Medians
• Recursive Star-Tree Parallel Data Structure
• Improved Bounds for Range Mode and Range Median Queries
• STACS 2005
• Lowest common ancestors in trees and directed acyclic graphs

This page was built for publication: Range mode and range median queries in constant time and sub-quadratic space