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

Simple item page
dc.creatorDominic, Saju Jude
dc.creatorSajith, G.
dc.date2004-04-13
dc.date.accessioned2026-07-07T03:21:07Z
dc.date.available2026-07-07T03:21:07Z
dc.descriptionIn 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.
dc.description13 pages with no figures, unpublished
dc.identifierhttps://arxiv.org/abs/cs/0404028
dc.identifierhttp://arxiv.org/abs/cs/0404028
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32076
dc.subjectData Structures and Algorithms
dc.subjectE1;F.2.2;G.3
dc.titleThe Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms
dc.typetext

Files

Collections

arXiv