Metraipolis › archive › dc_504ca38cae44

Optimal Encodings for Next/Previous Larger/Smaller Value Queries: A Unified Approach — arXiv:2610.38327

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.38327
License (as archived)
CC0-1.0
Archived
2026-11-01T02:46:27.146Z
SHA-256 of the archived text
02b90abacdac510a3a17afe206e8d89b774ae2b0f7198bf278739a0f1bf4fa85
Stable URL of this page
https://metraipolis.com/documento/dc_504ca38cae44

How to cite

Optimal Encodings for Next/Previous Larger/Smaller Value Queries: A Unified Approach — arXiv:2610.38327 — arXiv (en), https://arxiv.org/abs/2610.38327 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_504ca38cae44 (Metraipolis archive dc_504ca38cae44, sha256 02b90abacdac510a3a17afe206e8d89b774ae2b0f7198bf278739a0f1bf4fa85)
BibTeX
@misc{dc504ca38cae44,
  title = {Optimal Encodings for Next/Previous Larger/Smaller Value Queries: A Unified Approach — arXiv:2610.38327},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.38327},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_504ca38cae44; sha256 02b90abacdac510a3a17afe206e8d89b774ae2b0f7198bf278739a0f1bf4fa85},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.38327. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Given a 1D array over a total order and a query position in the array, a next larger value query returns the nearest position to the right whose value is larger than the value at the query position. Next smaller value queries and previous larger/smaller value queries are defined analogously. These queries are closely related to the $k$-th range minimum/maximum problem, which asks for the position of the $k$-th leftmost minimum/maximum value when the query range contains multiple minimum/maximum values. In this paper, we consider the encoding problem for answering any arbitrary subfamily of these four queries, where the queries must be answered without accessing the input array. We give a unified approach for obtaining space lower bounds for such encodings. We also obtain data structures for the query subfamilies that match the lower bounds up to lower-order additive terms, while supporting the queries in constant time. Our results generalize and improve several previous results on this problem [Gawrychowski and Nicholson, ICALP-2015; Jo and Satti, TCS-2016; Tsur, IPL-2019; Jo and Kim, Algorithmica-2025]. In addition, these results give tight bounds on the encoding complexity of all subfamilies of these queries for (1) permutations, (2) arrays without consecutive equal elements, and (3) general arrays.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.38327 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:17:58.591Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).