Predecessor Queries in Dynamic Integer Sets

Gerth Stølting Brodal

In Proc. 14th Annual Symposium on Theoretical Aspects of Computer Science, volume 1200 of Lecture Notes in Computer Science, pages 21-32. Springer Verlag, Berlin, 1997.

Abstract

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 loglog nf(n)≤ \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ε w) 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/loglog n) time while having worst case O(loglog n) update time.

Copyright notice

© Springer-Verlag Berlin Heidelberg 1997. All rights reserved.

Online version

stacs97.pdf (207 Kb)

DOI

10.1007/BFb0023445

Slides

stacs97.pdf (14326 Kb)

BIBTEX entry

@incollection{stacs97,
  author = "Gerth St{\o}lting Brodal",
  booktitle = "Proc. 14th Annual Symposium on Theoretical Aspects of Computer Science",
  doi = "10.1007/BFb0023445",
  isbn = "978-3-540-62616-9",
  pages = "21-32",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "Predecessor Queries in Dynamic Integer Sets",
  volume = "1200",
  year = "1997"
}