Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2007 Copyright 2007 Universität Bonn, Institut für Informatik, Abt. V
85282

13.07.2007

Predecessor Queries in Constant Time? (Revised Version)
Marek Karpinski and Yakov Nekrich
[Download PostScript] [Download PDF]

In this paper we design a new static data structure for batched predecessor queries. In particular, our data structure supports O(log1/2 n) queries in O(1) time per query and requires O(n &epsilon log1/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(np(N)) space for any p(N)=O( log log N).

Last Change: 12/05/07 at 09:35:58
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope