Space-efficient data structure for next/previous larger/smaller value queries

DOI10.1007/978-3-031-20624-5_5arXiv2209.00158OpenAlexW4312576536MaRDI QIDQ6163965

Geunho Kim, Seungbum Jo

Publication date: 26 July 2023

Published in: LATIN 2022: Theoretical Informatics (Search for Journal in Brave)

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

zbMATH Keywords

range minimum queriesbalanced parenthesis sequenceencoding model

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)

Cites Work

• Simultaneous encodings for range and next/previous larger/smaller value queries
• Combined data structure for previous- and next-smaller-values
• Representing trees of higher degree
• Succinct data structures for flexible text retrieval systems
• The effective entropy of next/previous larger/smaller value queries
• Waiting patterns for a printer
• Improved range minimum queries
• Space Efficient Suffix Trees
• Succinct Representation of Balanced Parentheses and Static Trees
• Fully Functional Static and Dynamic Succinct Trees
• Changing base without losing space
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• Optimal Encodings for Range Top-$$k$$, Selection, and Min-Max
• A unifying look at data structures
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
• Encoding Data Structures
• On Fixed Points of the Composite of Commuting Functions

This page was built for publication: Space-efficient data structure for next/previous larger/smaller value queries