Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2019) |
last year
(2018) |
two years ago
(2017) |
Notes URL
Action:
login to update
Options:
Goto entry point
Author, Editor
Author(s):
Brodal, Gerth Stølting
dblp
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
URL of the conference:
URL for downloading the paper:
Event Address*:
Lubeck, Germany
Language:
English
Event Date*
(no longer used):
February 27 - March 1, 1997
Organization:
Event Start Date:
16 October 2019
Event End Date:
16 October 2019
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
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