Dynamic range majority data structures

DOI10.1016/J.TCS.2016.07.039zbMATH Open1350.68068OpenAlexW2485167870MaRDI QIDQ306716FDOQ306716

Authors: Amr Elmasry, Meng He, J. Ian Munro, Patrick K. Nicholson 

Publication date: 1 September 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.07.039

Recommendations

• Dynamic range majority data structures
• Compressed dynamic range majority and minority data structures
• Range majority in constant time and linear space
• Range Majority in Constant Time and Linear Space
• Encodings for range majority queries
• A dynamic data structure for approximate range searching
• Optimal encodings for range majority queries
• Range majorities and minorities in arrays
• Computing and Combinatorics
• Opportunistic data structures for range queries

zbMATH Keywords

data structuresheavy hittersrange majorityrange queries

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Multidimensional divide-and-conquer
• Finding repeated elements
• Range majority in constant time and linear space
• Better space bounds for parameterized range majority and minority
• Array range queries
• Linear-space data structures for range minority query in arrays
• Range Majority in Constant Time and Linear Space
• Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization
• Surpassing the information theoretic bound with fusion trees
• Dynamic ordered sets with exponential search trees
• Space-efficient data-analysis queries on grids
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Approximate colored range and point enclosure queries
• Fusion trees can be implemented with \(AC^0\) instructions only
• Time bounds for selection
• The nearest common ancestor in a dynamic tree
• Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
• Indexing for summary queries
• Counting Colours in Compressed Strings
• Dynamic range majority data structures
• Dynamic range selection in linear space
• Space-efficient data-analysis queries on grids
• Data structures for approximate orthogonal range counting
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal External Memory Interval Management
• New Lower Bound Techniques for Dynamic Partial Sums and Related Problems

Cited In (4)

• Dynamic range majority data structures
• Range Majority in Constant Time and Linear Space
• Range majorities and minorities in arrays
• Compressed dynamic range majority and minority data structures

This page was built for publication: Dynamic range majority data structures

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