Space-efficient data structure for next/previous larger/smaller value queries
The article presents a new, space-efficient encoding data structure designed to support various range and value queries on an array of size \(n\). The key focus is on achieving a balance between minimal space usage and efficient query time within the encoding model, where queries must be answered without access to the original input array.\N\NThe proposed data structure combines the Balanced Parenthesis (BP) sequences of the colored 2d-min heap and 2d-max heap of the input array, utilizing \((3.701n + o(n))\) bits for general arrays. This matches the current best theoretical upper bound [\textit{D. Tsur}, Inf. Process. Lett. 145, 39--43 (2019; Zbl 1446.68047)], but improves upon it by providing efficient query support, which previous models lacked. Furthermore, the space requirement can be reduced to \((3.585n + o(n))\) bits if the array does not contain two consecutive equal elements. While some previous models (e.g., [\textit{J. Fischer} and \textit{V. Heun}, SIAM J. Comput. 40, No. 2, 465--492 (2011; Zbl 1222.05024)]) offer \(O(1)\) query time, they often require significantly more space (up to \(5.08n\) bits). The authors' structure is notably more space-efficient, although with a slightly slower query time for specific operations like \(q\)-th minimum or next smaller value.\N\NIn conclusion, the paper represents a significant advancement in succinct data structures. It successfully matches the best-known space bounds while ensuring that essential range and relative value queries are performed in near-constant time, making it a valuable contribution to the field.
- 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)
