Predecessor Queries in Dynamic Integer Sets

Brodal, Gerth Stølting

Local TagsRelease HistoryDetailsSummary

Predecessor Queries in Dynamic Integer Sets

Brodal, G. S. (1997). Predecessor Queries in Dynamic Integer Sets. In R. Reischuk, & M. Morvan (Eds.), Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS-97) (pp. 21-32). Berlin, Germany: Springer.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3976-8 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-3978-4

Genre: Conference Paper

Files

show Files

Locators

show

Creators

show

hide

Creators:
Brodal, Gerth Stølting¹, Author

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

Content

show

hide

Free keywords: -

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.

Details

show

hide

Language(s): eng - English

Dates: Modified: 2010-03-02Date issued: 1997

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: -

Identifiers: eDoc: 517862
Other: Local-ID: C1256428004B93B8-D3863CDFD46B3270C12565B70057192D-Brodal97a

Degree: -

Event

show

hide

Title: Untitled Event

Place of Event: Lubeck, Germany

Start-/End Date: 1997

Legal Case

show

Project information

show

Source 1

show

hide

Title: Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science (STACS-97)

Source Genre: Proceedings

Creator(s):
Reischuk, Rudiger, Editor
Morvan, Michel, Editor

Affiliations:
-

Publ. Info: Berlin, Germany : Springer

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 21 - 32 Identifier: ISBN: 3-540-62616-6

Source 2

show

hide

Title: Lecture Notes in Computer Science

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 1200 Sequence Number: - Start / End Page: - Identifier: -