In this paper we design a new static data structure for batched predecessor queries. In particular, our data structure supports O((log n)~(1/2)) queries in O(1) time per query and requires O(n~(ε(log n)~(1/2))) space for any ε > 0. This is the first o(N) space and O(1) amortized time data structure for arbitrary N = Ω(n~(ε(log n)~(1/2))) 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~(ε log log N)) space for any ε > 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 n)~(1/2))/p(n)) time per query and requires O(n~(p(n))) space for any p(n) = O((log n)~(1/2)), 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).
展开▼
