Range majorities and minorities in arrays

DOI10.1007/s00453-021-00799-7OpenAlexW3138213727MaRDI QIDQ2032347

J. Ian Munro, Travis Gagie, Gonzalo Navarro, Yakov Nekrich, Djamal Belazzougui

Publication date: 11 June 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.04495

zbMATH Keywords

compressed data structuresrange majority and minorityrange mode

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (2)

Compressed dynamic range majority and minority data structures ⋮ Path queries on functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear-space data structures for range frequency queries on arrays and trees
• Optimal encodings for range majority queries
• Dynamic range majority data structures
• Efficient fully-compressed sequence representations
• Linear-space data structures for range minority query in arrays
• A simple storage scheme for strings achieving entropy bounds
• Succinct data structures for flexible text retrieval systems
• Range mode and range median queries in constant time and sub-quadratic space
• Approximate colored range and point enclosure queries
• Finding repeated elements
• Range majority in constant time and linear space
• Fast compressed self-indexes with deterministic linear-time construction
• Compressed dynamic range majority and minority data structures
• Linear-space data structures for range mode query in arrays
• Optimal query time for encoding range majority
• Better Space Bounds for Parameterized Range Majority and Minority
• Compressed representations of sequences and full-text indexes
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Cell Probe Lower Bounds and Approximations for Range Mode
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• Alphabet-Independent Compressed Text Indexing
• Optimal Lower and Upper Bounds for Representing Sequences
• Linear-time String Indexing and Analysis in Small Space
• Space-Efficient Framework for Top-k String Retrieval Problems
• More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
• Theory and practice of monotone minimal perfect hashing
• Improved Bounds for Range Mode and Range Median Queries
• STACS 2005

This page was built for publication: Range majorities and minorities in arrays