The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms

Details The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms

2004-04-13

arxiv.org/abs/cs/0404028v1

Computer Science

Data Structures and Algorithms

13 pages with no figures, unpublished

Scientific paper

In this paper, we present a probabilistic self-balancing dictionary data structure for massive data sets, and prove expected amortized I/O-optimal bounds on the dictionary operations. We show how to use the structure as an I/O-optimal priority queue. The data structure, which we call as the random buffer tree, abstracts the properties of the random treap and the buffer tree and has the same expected I/O-bounds as the buffer tree.

Affiliated with

Also associated with

No associations

Rating

The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-247150