Dynamic range majority data structures

DOI10.1016/J.TCS.2016.07.039MaRDI QIDQ306716zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

data structuresheavy hittersrange majorityrange queries

Mathematics Subject Classification ID

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

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

Cites work

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

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)