Linear-space data structures for range minority query in arrays

DOI10.1007/S00453-014-9881-9MaRDI QIDQ494786zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Stephane Durocher, Matthew Skala, Bryan T. Wilkinson

Publication date 2 September 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-014-9881-9

zbMATH Keywords

data structuresrange queriesleast frequent elementminority

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Linear-space data structures for range minority query in arrays
• Linear-space data structures for range frequency queries on arrays and trees
• Linear-space data structures for range frequency queries on arrays and trees
• Range Majority in Constant Time and Linear Space
• Range majority in constant time and linear space

Cites work

• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• scientific article; zbMATH DE number 2226802 (Why is no real title available?)
• Cell probe lower bounds and approximations for range mode
• Dynamic range majority data structures
• Filtering Search: A New Approach to Query-Answering
• Fully-functional succinct trees
• Improved Bounds for Range Mode and Range Median Queries
• Linear-space data structures for range minority query in arrays
• Linear-space data structures for range mode query in arrays
• Making data structures persistent
• On Cartesian Trees and Range Minimum Queries
• Persistent predecessor search and orthogonal point location on the word RAM
• Range Majority in Constant Time and Linear Space
• Range mode and range median queries in constant time and sub-quadratic space
• Range selection and median: tight cell probe lower bounds and adaptive data structures
• STACS 2005
• Towards optimal range medians

Cited in

(10)

• Range Majority in Constant Time and Linear Space
• Array range queries
• Range majorities and minorities in arrays
• Tree path majority data structures
• Compressed dynamic range majority and minority data structures
• Linear-space data structures for range minority query in arrays
• On space efficient two dimensional range minimum data structures
• Linear-space data structures for range frequency queries on arrays and trees
• Improved time and space bounds for dynamic range mode
• Linear-space data structures for range frequency queries on arrays and trees

This page was built for publication: Linear-space data structures for range minority query in arrays

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