MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Brodal, Gerth Støltingdblp
Editor(s):
Reischuk, Rudiger
Morvan, Michel
dblp
dblp
BibTeX cite key*:
Brodal97a
Title, Booktitle
Title*:
Predecessor Queries in Dynamic Integer Sets
Booktitle*:
Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS-97)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Lubeck, Germany
Language:
English
Event Date*
(no longer used):
February 27 - March 1, 1997
Organization:
Event Start Date:
28 November 2020
Event End Date:
28 November 2020
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1200
Number:
Month:
Pages:
21-32
Year*:
1997
VG Wort Pages:
ISBN/ISSN:
3-540-62616-6
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
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.
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Brodal97a,
AUTHOR = {Brodal, Gerth Stølting},
EDITOR = {Reischuk, Rudiger and Morvan, Michel},
TITLE = {Predecessor Queries in Dynamic Integer Sets},
BOOKTITLE = {Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS-97)},
PUBLISHER = {Springer},
YEAR = {1997},
VOLUME = {1200},
PAGES = {21--32},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Lubeck, Germany},
ISBN = {3-540-62616-6},
}


Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Gerth Stolting Brodal
Created
02/26/1998 04:51:20 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm
Uwe Brahm
Edit Dates
04/02/98 03:44:02 PM
04/02/98 02:16:48 PM
02/26/98 06:50:42 PM
02/26/98 06:37:06 PM
26/02/98 16:51:21