Optimal encodings for range majority queries

DOI10.1007/S00453-015-9987-8zbMath1332.68035arXiv1404.2677OpenAlexW2148145672MaRDI QIDQ270016

Sharma V. Thankachan, Gonzalo Navarro

Publication date: 6 April 2016

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

encoding data structuresrange majority queriessuccinct data structures

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (2)

Compressed dynamic range majority and minority data structures ⋮ Range majorities and minorities in arrays

Cites Work

• Unnamed Item
• Unnamed Item
• Range mode and range median queries in constant time and sub-quadratic space
• Range majority in constant time and linear space
• Better Space Bounds for Parameterized Range Majority and Minority
• Array Range Queries
• Encodings for Range Selection and Top-k Queries
• Linear-Space Data Structures for Range Minority Query in Arrays
• Time-space trade-offs for predecessor search
• Asymptotically Optimal Encodings for Range Selection
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Constructing Efficient Dictionaries in Close to Sorting Time
• Cell Probe Lower Bounds and Approximations for Range Mode
• Online Sorted Range Reporting
• Recursive Star-Tree Parallel Data Structure
• Efficient Storage and Retrieval by Content and Address of Static Files
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Encodings for Range Majority Queries
• Practical Entropy-Compressed Rank/Select Dictionary
• STACS 2005
• Adaptive and Approximate Orthogonal Range Counting

This page was built for publication: Optimal encodings for range majority queries