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

DOI10.1007/S00453-025-01325-9MaRDI QIDQ6932710zbMATH OpenFDO

Authors Seungbum Jo, Geunho Kim

Publication date 8 September 2025

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00453-025-01325-9

zbMATH Keywords

balanced parenthesis sequenceencoding modelrange-minimum queriessuccinct data structures

Mathematics Subject Classification ID

Data structures (68P05)

Cites work

• A unifying look at data structures
• Changing base without losing space
• Combined data structure for previous- and next-smaller-values
• Encoding data structures
• Fully functional static and dynamic succinct trees
• Improved range minimum queries
• On Fixed Points of the Composite of Commuting Functions
• Optimal Doubly Logarithmic Parallel Algorithms Based On Finding All Nearest Smaller Values
• Optimal encodings for range top-\(k\), selection, and min-max
• Representing trees of higher degree
• Simultaneous encodings for range and next/previous larger/smaller value queries
• Space efficient suffix trees
• Space-efficient data structure for next/previous larger/smaller value queries
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Succinct data structures for flexible text retrieval systems
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct representation of balanced parentheses and static trees
• The effective entropy of next/previous larger/smaller value queries
• Waiting patterns for a printer

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6932710)