2004/04/13 by Saju Jude Dominic, Dominic, Saju Jude, G. Sajith +1
Computer Science · #Advanced Data Storage Technologies #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #E1 #F.2.2 #FOS: Computer and information sciences #G.3 #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0404028
13 pages with no figures, unpublished
arxiv created 2004/04/13 · openalex publication_date 2004/04/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.