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

DOI10.1016/J.IPL.2008.10.007zbMATH Open1191.68343OpenAlexW2090221650MaRDI QIDQ976080FDOQ976080

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

Recommendations

• Improved Bounds for Range Mode and Range Median Queries
• STACS 2005
• Linear-space data structures for range mode query in arrays
• Towards optimal range medians
• Linear-space data structures for range mode query in arrays

zbMATH Keywords

algorithmscomputational complexitytheory of computation

Mathematics Subject Classification ID

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

Cites Work

• Recursive Star-Tree Parallel Data Structure
• Title not available (Why is that?)
• Lowest common ancestors in trees and directed acyclic graphs
• STACS 2005
• Fast Algorithms for Finding Nearest Common Ancestors
• Range Medians
• Improved Bounds for Range Mode and Range Median Queries

Cited In (15)

• Title not available (Why is that?)
• Colored range queries and document retrieval
• Optimal encodings for range majority queries
• Towards optimal range medians
• Improved Bounds for Range Mode and Range Median Queries
• STACS 2005
• New algorithms on wavelet trees and applications to information retrieval
• Enumerating Range Modes
• Linear-space data structures for range mode query in arrays
• Low space data structures for geometric range mode query
• Algorithms and Computation
• Array Range Queries
• Range Majority in Constant Time and Linear Space
• Linear-space data structures for range minority query in arrays
• Range majorities and minorities in arrays

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

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