Design a data structure with constant insertion and sublinear range maximum query

Question

Suppose we have access to a stream of ordered pairs, where the $i^{\text{th}}$ element in the stream is an ordered pair $(a_i, b_i)$, where $a_i$ is a timestamp and $b_i$ is an arbitrary real. How can we design a data structure with the following two methods:

1. $\mathcal{O}(1)$ insert
2. Sublinear lookup to determine when, given some timestamp $q$ as an argument, find the maximum value of $b_i$ for all elements $(a_i, b_i)$ already in our data structure with $a_i$ in the range $(q-1, q)$.

Note: The $a_i$'s are not necessarily in sorted order in the stream. There are no additional assumptions about the the distribution of the timestamps or the values $b_i$. While I am looking for a solution with worst-case time complexity for both methods, I would also be interested in seeing if the data structure could be achieved in amortized time complexity for each or both methods.

Answer 1

If they're timestamps, there's a good chance they are approximately randomly distributed across some range, say $[\ell,u]$. In this case there exist reasonable solution.

You can hash each pair into $k$ equal-width buckets in this range, i.e., using the hash function $h(a,b) = \lfloor N(a-\ell)/(u-\ell) \rfloor$, where $k$ is roughly similar to the number of items seen so far. Within a bucket, remember the largest value of $b$ of all pairs that hashed into that bucket. Then insert can be done in $O(1)$ expected time, and lookup can be done in $O(1)$ expected time.

Of course, we won't know $[\ell,u]$ exactly, and $\ell,u,k$ will change over time. However you can adjust on the fly, by keeping track of the smallest and largest timestamp seen and the number of pairs seen so far. Every time the number of pairs doubles, you update the hash function and rehash. Naively, that sounds like it takes $O(n)$ time to rehash, but you can spread that out over the next $n/4$ inserts, maintaining the $O(1)$ expected running time.

---

If the timestamps aren't uniformly distributed but they come iid from some distribution, and the distribution is "smooth" enough, then I think you can find a similar solution. Keep track of the integer-percentiles of the $a$ values (i.e., the 0% percentile value, the 1% percentile value, the 2% percentile value, and so on); it is possible to estimate these values using streaming quantile estimation / streaming histogram estimation. To hash a pair, convert its $a$ value to a percentile (a real number $p$ in the range $[0,1]$), using linear interpolation among these 101 known percentile values; then $p$ will be approximately uniformly distributed on $[0,1]$, and you can hash $p$ into equal-width buckets as before. If the distribution is smooth enough, linear interpolation will work well and $p$ will be approximately uniformly distributed. If the distribution is not smooth, this may work poorly.