Linear-space data structures for range frequency queries on arrays and trees

DOI10.1007/s00453-014-9947-8zbMath1411.68034OpenAlexW1977261082MaRDI QIDQ261369

Matthew Skala, Sharma V. Thankachan, Rahul Shah, Stephane Durocher

Publication date: 23 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.719.2566

zbMATH Keywords

frequencydata structureslinear spacecolor querypath queryrange query

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (4)

Unnamed Item ⋮ Range majorities and minorities in arrays ⋮ Tree path majority data structures ⋮ Data structures for categorical path counting queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Colored range queries and document retrieval
• Towards optimal range medians
• Preserving order in a forest in less than logarithmic time and linear space
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• A simple linear-space data structure for constant-time range minimum query
• A data structure for dynamic trees
• Range majority in constant time and linear space
• Linear-space data structures for range mode query in arrays
• Low space data structures for geometric range mode query
• Succinct representations of weighted trees supporting path queries
• Improved compressed indexes for full-text document retrieval
• Better Space Bounds for Parameterized Range Majority and Minority
• Array Range Queries
• Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees
• Linear-Space Data Structures for Range Minority Query in Arrays
• New Lower and Upper Bounds for Representing Sequences
• Succinct Data Structures for Path Queries
• Succinct Representations of Binary Trees for Range Minimum Queries
• Range Majority in Constant Time and Linear Space
• Path Queries in Weighted Trees
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Optimal Succinctness for Range Minimum Queries
• On Cartesian Trees and Range Minimum Queries
• Towards Optimal Range Medians
• Hash, Displace, and Compress
• Filtering Search: A New Approach to Query-Answering
• Space-Efficient Framework for Top-k String Retrieval Problems
• Algorithms and Computation
• Lowest common ancestors in trees and directed acyclic graphs

This page was built for publication: Linear-space data structures for range frequency queries on arrays and trees