13.07.2007

In this paper we design a new static data structure for batched predecessor queries. In particular, our data structure supports O(log^1/2 n) queries in O(1) time per query and requires O(n ^&epsilon log^1/2 n ) space for any &epsilon > 0. This is the first o(N) space and O(1) amortized time data structure for arbitrary N and n where N is the size of the universe. We also present a data structure that answers O( log log N) predecessor queries in O(1) time per query and requires O(n^&epsilon log log N) space for any &epsilon > 0. The method of solution relies on a certain way of searching for predecessors of all elements of the query in parallel.

In a general case, our approach leads to a data structure that supports p(n) queries in O( log ^1/2 n/p(n)) time per query and requires O(n ^p(n)) space for any p(n)=O( log ^1/2 n), and a data structure that supports p(N) queries in O( log log N/p(N)) time per query and requires O(n^p(N)) space for any p(N)=O( log log N).