A Lower Bound on Supporting Predecessor Search in $k$ sorted Arrays

Abstract

We seek to perform efficient queries for the predecessor among $n$ values stored in $k$ sorted arrays. Evading the $\Omega (n\log k)$ lower bound from merging $k$ arrays, we support predecessor queries in $O(\log n)$ time after $O(n\log (\frac{k}{\log n}))$ construction time. By applying Ben-Or's technique, we establish that this is optimal for strict predecessor queries, i.e., every data structure supporting $O(\log n)$-time strict predecessor queries requires $\Omega (n\log (\frac{k}{\log n}))$ construction time. Our approach generalizes as a template for deriving similar lower bounds on the construction time of data structures with some desired query time.

This work was presented at the Young Researcher Workshop on Automata, Languages and Programming (YR-ICALP 2015), July 5th, 2015 in Kyoto, Japan