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

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

14.04.2005

Predecessor Queries in Constant Time?
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: 04/14/05 at 10:40:46
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope