Range Majority in Constant Time and Linear Space

DOI10.1007/978-3-642-22006-7_21zbMath1332.68032OpenAlexW2223854644MaRDI QIDQ3012810

Meng He, J. Ian Munro, Stephane Durocher, Matthew Skala, Patrick K. Nicholson

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22006-7_21

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

Dynamic range majority data structures ⋮ Space-efficient data-analysis queries on grids ⋮ Linear-space data structures for range minority query in arrays ⋮ Linear-space data structures for range mode query in arrays ⋮ Array Range Queries ⋮ Linear-space data structures for range frequency queries on arrays and trees

Uses Software

• Stony Brook

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Range mode and range median queries in constant time and sub-quadratic space
• Determining the mode
• Finding repeated elements
• Variants of the majority problem.
• Cell Probe Lower Bounds and Approximations for Range Mode
• Sorting and Searching in Multisets
• An improved data stream summary: the count-min sketch and its applications
• Determining plurality
• Improved Bounds for Range Mode and Range Median Queries
• STACS 2005