Encoding 2D range maximum queries

DOI10.1016/j.tcs.2015.10.012zbMath1331.68060arXiv1109.2885MaRDI QIDQ897899

Mordecai J. Golin, Srinivasa Rao Satti, Danny Krizanc, John Iacono, Rajeev Raman, Sunil M. Shende, S. Srinivasa Rao

Publication date: 8 December 2015

Published in: Theoretical Computer Science, Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

encoding model; indexing model; Cartesian trees; effective entropy; range maximum queries

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

68P05: Data structures

Related Items

Unnamed Item, An Encoding for Order-Preserving Matching., Two dimensional range minimum queries and Fibonacci lattices, Simultaneous encodings for range and next/previous larger/smaller value queries, Encoding nearest larger values, The effective entropy of next/previous larger/smaller value queries, A simple linear-space data structure for constant-time range minimum query, Linear-space data structures for range mode query in arrays, Space efficient data structures for nearest larger neighbor, Encoding two-dimensional range top-\(k\) queries, Orthogonal Range Searching for Text Indexing, Succinct Representations of Ordinal Trees, Range Minimum Query Indexes in Higher Dimensions, Encoding Nearest Larger Values, Space Efficient Data Structures for Nearest Larger Neighbor

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On space efficient two dimensional range minimum data structures
• Representing trees of higher degree
• A simple optimal representation for balanced parentheses
• Compressed suffix trees with full functionality
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Two-Dimensional Range Minimum Queries
• A Uniform Approach Towards Succinct Representation of Trees
• Indexing compressed text
• On Cartesian Trees and Range Minimum Queries
• A unifying look at data structures
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching