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:








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:

26 August 2019

Event End Date:

26 August 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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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