Optimal data structures answer nearest larger or smaller value queries quickly
Optimal Encodings for Next/Previous Larger/Smaller Value Queries: A Unified Approach
Data Structures and Algorithms
Summary
This paper studies how to store information so that given a position in a list of numbers, you can quickly find the nearest bigger or smaller number either before or after it. The researchers figured out the smallest amount of data needed to do this and made fast methods that use this minimal data amount. Their work improves and unifies earlier findings and works for different types of number lists, including those with unique numbers or with no repeated neighbors.
What this means in practice
- •For database engineers: Build indexing structures that answer nearest larger or smaller value queries on ordered data quickly without storing the original array.
- •For game developers: Optimize computations involving nearest value queries in game state arrays while minimizing memory usage.
Authors
Seungbum Jo, Geunho Kim, Kunihiko Sadakane, Srinivasa Rao Satti
Abstract
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.