Aarhus University Seal

Predecessor queries in dynamic integer sets

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
We consider the problem of maintaining a set of n integers in the range 0.2w–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 n \leqslant f(n) \leqslant Ö{log n} Unknown control sequence '\leqslant'. A data structure is presented supporting insertions and deletions in worst case O(f(n)) time, predecessor queries in worst case O((logn)/f(n)) time and minimum and maximum queries in worst case constant time. The required space is O(n2w ) for an arbitrary constant > 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.
Original languageEnglish
Title of host publicationSTACS 97 : 14th Annual Symposium on Theoretical Aspects of Computer Science Lübeck, Germany February 27–March 1, 1997 Proceedings
EditorsRüdiger Reischuk, Michel Morwan
Number of pages12
Publication year1997
ISBN (print)978-3-540-62616-9
Publication statusPublished - 1997
Event14th Annual Symposium on Theoretical Aspects of Computer Science. STACS 1997 - Lübeck, Germany
Duration: 27 Feb 19971 Mar 1997


Conference14th Annual Symposium on Theoretical Aspects of Computer Science. STACS 1997
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 34728266