Linear-space data structures for range minority query in arrays

DOI10.1007/S00453-014-9881-9zbMATH Open1319.68063OpenAlexW2155992938MaRDI QIDQ494786FDOQ494786

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

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

zbMATH Keywords

data structuresrange queriesleast frequent elementminority

Mathematics Subject Classification ID

Data structures (68P05)

Cites Work

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

Cited In (10)

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

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)