Search

We present efficient fully persistent B-trees in the I/O model with block size B that support range searches on t reported elements at any accessed version of size n in O (log B ⁡ n + t / B) I/Os and updates at any accessed version in O (log B ⁡ n + log 2 ⁡ B) amortized I/Os, using O (m / B) disk blocks after m updates. This improves both the query and update I/O-efficiency of the previous fully persistent B-trees of Lanka and Mays (ACM SIGMOD ICMD 1991). To achieve the result, we introduce an implementation for ephemeral B-trees that supports searches and updates in O (log B ⁡ n) I/Os, using O (n / B) blocks, where moreover every update makes a worst-case constant number of modifications to the structure. We make these B-trees fully persistent using an I/O-efficient method for full persistence, inspired by the node-splitting method of Driscoll et al. (JCSS 1989). Interesting in its own right, the method is generic enough to be applied to any external memory pointer-based data structure with maximum in-degree d i n and out-degree O (B) , where every node occupies a constant number of blocks on disk. For a user-specified parameter π = Ω (d i n) , we achieve O (π B + log 2 ⁡ π) I/O-overhead per access to a field of an ephemeral block and amortized O (π B + log 2 ⁡ π + d i n π log 2 ⁡ B) I/O-overhead and O (1 / B) block space-overhead per modification to the ephemeral structure. [ABSTRACT FROM AUTHOR]

We present the first static and dynamic external memory data structures for variants of 2-d orthogonal range skyline reporting with worst-case logarithmic query and update I/O-complexity. The results are obtained by using persistent data structures and by extending the attrition priorities queues of Sundar (1989) [26] to also support real-time concatenation, a result of independent interest. We show that the problem is as hard as standard 2-d orthogonal range reporting in the indexability model by a lower bound on the I/O-complexity of 2-d orthogonal anti-dominance skyline reporting queries. [ABSTRACT FROM AUTHOR]