
Universität Bonn > Institut für Informatik > Abteilung V  
CSReports 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(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. 

Last Change:
04/14/05 at 10:40:46
English 
Universität Bonn > Institut für Informatik > Abteilung V 