Dynamic Data Structure for Sliding Window of varying size with Predecessor queries

Question

I was wondering if anyone can point me to a data structure that supports the following operations. Goal is to create a data structure $D$ that stores 64-bit integers and provides the following operations:

• min() in $O(1)$ worst-case time
• max() in $O(1)$ worst-case time
• predecessor($x$) find the greatest element $y \in D$ such that $y \leq x $ in $O(\log \|D\|)$ worst-case time
• add($x$) in $O(1)$ worst-case time under the variant that $x \geq \max()$. When $x = \max()$, this can just be a no-op, so can effectively be ignored since max() can be done in $O(1)$ time. In other words, $D$ is essentially a set.
• splice($x$) remove from $D$ all of the elements $y$ such that $y \leq x$. This should take worst-case time proportional to the number of elements removed (i.e. amortized $O(1)$ per element removed).

I don't have explicit space constraints, but I would prefer a linear space data structure.

A doubly-linked list can provide all of these requirements except for the predecessor query in the desired time. On the other hand, tree structures can provide the predecessor query with the desired time, but don't take advantage of the fact that the data inserted is non-decreasing. So insertions and deletions fall short. A circular-array seems like a close bet, but my window does not have a fixed size, and insertions really should take $O(1)$ worst-case time.

Is this doable? If insertions were arbitrary, then this would clearly reduce to sorting... but in my case, the data inserted appears in sorted order.

I also noticed that a predecessor query can be reformulated in terms of a rank query followed by a select query, but I haven't been able to exploit existing dynamic rank-and-select data structures for this purpose.

Answer 1

One pragmatic approach is to use a dynamic array $A$. Store the integers in sorted order in this array. Augment this data structure with two additional indices: $i_\min$ (the index of the smallest element in the set), and $i_\max$ (the index of the largest element in the set, plus one).

Then, the predecessor operation can be implemented through binary search in $A[i_\min \dots i_\max-1]$. The min and max operations are trivial. The add operation involves potentially appending to the end of the array. Splice involves finding the index of $x$ in the array, then updating $i_\min$ to point to that index.

This gets close to your desired running times. Min and max run in $O(1)$ worst-case time. Predecessor runs in $O(\log \|D\|)$ time, worst-case. Add takes $O(1)$ amortized time, assuming you use standard implementations of dynamic arrays. Splice can be implemented so its running time is linear in the number of elements deleted (if you use a linear scan starting from $i_\min$); in fact, you can implement it in time logarithmic in the number of elements deleted (by using exponential search followed by binary search to find $x$). I suspect this might be good enough for practical purposes.

The exact running time will depend on what you assume about the API to the memory allocator and virtual memory subsystem and what you assume about their running time. For instance, do you assume that you can use sbrk and it runs in constant time? Also, basic memory operations like malloc() probably actually take logarithmic time (because of the need to manipulate page tables, which are a tree data structure with log-time access), even though in algorithm analysis we typically treat them as taking constant time. So it gets tricky, if you care about practical use of these data structures.

A pragmatic comment: once you get into data structures where you are comparing between constant time and logarithmic time, the memory hierarchy (L1 cache, L2 cache, etc.) starts to have a big impact and a logarithmic-time data structure that is memory hierarchy friendly can potentially perform better than a constant-time data structure that interacts poorly with the memory hierarchy. Given that you seem to care a lot about the difference between constant time and log-time, if this is a practical problem, you might be in a situation where it's worth expanding your scope to consider multiple data structures, even if some operations take log-time, and benchmark how efficient each one is on the types of workloads that arise for you in practice.