Deterministic data structure enables fast weighted increasing subsequence queries
Near-Linear Preprocessing for Range Weighted Longest Increasing Subsequence Queries
Data Structures and Algorithms
Summary
Finding the longest increasing sequence within a range of data points is a common problem, especially when each point has a weight. The authors created a method that prepares the data quickly and then answers queries about these sequences in much less time than before. Their approach works by using a special property of the data that allows them to combine partial solutions efficiently. This means you can now find and report important sequences faster, which was previously thought to need much more time.
What this means in practice
- •For database engineers: Speed up queries that require finding weighted increasing sequences within data ranges enabling more efficient analytics on ordered datasets.
- •For algorithm developers: Implement faster algorithms for problems involving weighted sequence comparisons by using this data structure for improved preprocessing and query times.
Authors
Keisuke Korogi
Abstract
We give a deterministic data structure for range weighted longest increasing subsequence (LIS) queries on $n$ values with positive weights. Preprocessing takes $O(n\log^2 n)$ time and space. Value queries take $O(\log n)$ time, and an optimal subsequence of $k$ elements can be reported in $O(k + \log n)$ time. This resolves an open question on truly subquadratic preprocessing with polylogarithmic query time. The key is a single-crossing property of envelopes for value-separated endpoint sets, enabling $O(\log n)$-time persistent merges. The bounds assume constant-time exact addition and comparison of weights.