de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Predecessor Queries in Dynamic Integer Sets

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44187

Brodal,  Gerth Stølting
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Brodal, G. S. (1997). Predecessor Queries in Dynamic Integer Sets. In R. Reischuk, & M. Morvan (Eds.), Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS-97) (pp. 21-32). Berlin, Germany: Springer.

We consider the problem of maintaining a set of $n$ integers in the range $0..2^{w}-1$ under the operations of insertion, deletion, predecessor queries, minimum queries and maximum queries on a unit cost RAM with word size $w$ bits. Let $f(n)$ be an arbitrary nondecreasing smooth function satisfying $\log\log n\leq f(n)\leq \sqrt{\log n}$. A data structure is presented supporting insertions and deletions in worst case $O(f(n))$ time, predecessor queries in worst case $O((\log n)/f(n))$ time and minimum and maximum queries in worst case constant time. The required space is $O(n2^{\epsilon w})$ for an arbitrary constant $\epsilon>0$. The RAM operations used are addition, arbitrary left and right bit shifts and bit-wise boolean operations. The data structure is the first supporting predecessor queries in worst case $O(\log n/\log\log n)$ time while having worst case $O(\log\log n)$ update time.