Range Majority in Constant Time and Linear Space

DOI10.1007/978-3-642-22006-7_21MaRDI QIDQ3012810zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Range majority in constant time and linear space
• Better space bounds for parameterized range majority and minority
• Approximate range emptiness in constant time and optimal space
• Nonerasing, counting, and majority over the linear time hierarchy
• Randomized range-maxima in nearly-constant parallel time
• Dynamic range majority data structures
• Dynamic range majority data structures
• Optimal encodings for range majority queries
• Linear-space data structures for range minority query in arrays
• Linear-space data structures for range minority query in arrays

Cites work

• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 2226802 (Why is no real title available?)
• An improved data stream summary: the count-min sketch and its applications
• Cell probe lower bounds and approximations for range mode
• Determining plurality
• Determining the mode
• Finding repeated elements
• Improved Bounds for Range Mode and Range Median Queries
• Linear-space data structures for range mode query in arrays
• Range mode and range median queries in constant time and sub-quadratic space
• STACS 2005
• Sorting and Searching in Multisets
• The algorithm design manual
• Variants of the majority problem.

Cited in

(15)

• Linear-space data structures for range frequency queries on arrays and trees
• Linear-space data structures for range frequency queries on arrays and trees
• Optimal encodings for range majority queries
• Linear-space data structures for range minority query in arrays
• Space-efficient data-analysis queries on grids
• Dynamic range majority data structures
• Dynamic range majority data structures
• Better space bounds for parameterized range majority and minority
• Array range queries
• Range majority in constant time and linear space
• Encodings for range majority queries
• Optimal query time for encoding range majority
• Linear-space data structures for range mode query in arrays
• Linear-space data structures for range minority query in arrays
• Range majorities and minorities in arrays

Describes a project that uses

Uses Software

• Stony Brook

This page was built for publication: Range Majority in Constant Time and Linear Space

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