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.