The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms
<|reference_start|>The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms: 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.<|reference_end|>
@article{dominic2004the,
    title={The Random Buffer Tree : A Randomized Technique for I/O-efficient
  Algorithms},
    author={Saju Jude Dominic and G. Sajith},
    journal={arXiv preprint arXiv:cs/0404028},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0404028},
    primaryClass={cs.DS}
}