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: 18 October 2019 Event End Date: 18 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:

 (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},