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

DOI10.1016/J.IPL.2008.10.007MaRDI QIDQ976080zbMATH OpenOpenAlexFDO

Authors 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)

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

Cites work

• scientific article; zbMATH DE number 2226802 (Why is no real title available?)
• Fast Algorithms for Finding Nearest Common Ancestors
• Improved Bounds for Range Mode and Range Median Queries
• Lowest common ancestors in trees and directed acyclic graphs
• Range Medians
• Recursive Star-Tree Parallel Data Structure
• STACS 2005

Cited in

(15)

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

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)