Linear-space data structures for range mode query in arrays
From MaRDI portal
Publication:2254510
DOI10.1007/s00224-013-9455-2zbMath1319.68062WikidataQ57009369 ScholiaQ57009369MaRDI QIDQ2254510
Timothy M. Chan, Bryan T. Wilkinson, Stephane Durocher, Jason Morrison, Kasper Green Larsen
Publication date: 5 February 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2012/3425/
68P05: Data structures
Related Items
Range closest-pair search in higher dimensions, Linear-space data structures for range frequency queries on arrays and trees, Tree path majority data structures, Compressed dynamic range majority and minority data structures, Ranked document selection
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal partition trees
- Towards optimal range medians
- Finding range minima in the middle: approximations and applications
- Range searching with efficient hierarchical cuttings
- Encoding 2D range maximum queries
- Succinct data structures for flexible text retrieval systems
- Range mode and range median queries in constant time and sub-quadratic space
- Determining the mode
- Cutting hyperplanes for divide-and-conquer
- Preserving order in a forest in less than logarithmic time and linear space
- A simple linear-space data structure for constant-time range minimum query
- Range majority in constant time and linear space
- Towards polynomial lower bounds for dynamic problems
- Linear-Space Data Structures for Range Minority Query in Arrays
- Two Dimensional Range Minimum Queries and Fibonacci Lattices
- Succinct Representations of Binary Trees for Range Minimum Queries
- Range Majority in Constant Time and Linear Space
- Dynamic Range Majority Data Structures
- Dynamic Range Selection in Linear Space
- Two-Dimensional Range Minimum Queries
- Range Medians
- Optimal Succinctness for Range Minimum Queries
- On Space Efficient Two Dimensional Range Minimum Data Structures
- Cell Probe Lower Bounds and Approximations for Range Mode
- Orthogonal Range Searching in Linear and Almost-Linear Space
- A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array
- On Cartesian Trees and Range Minimum Queries
- Towards Optimal Range Medians
- Data Structures for Range Median Queries
- On the Complexity of Maintaining Partial Sums
- Sorting and Searching in Multisets
- Regularity Lemmas and Combinatorial Algorithms
- Algorithms and Computation
- Path Minima Queries in Dynamic Weighted Trees
- Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
- The cell probe complexity of dynamic range counting
- Multiplying matrices faster than coppersmith-winograd
- Improved Bounds for Range Mode and Range Median Queries
- STACS 2005
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting