Search

Abstract: We present a set of time-efficient approaches to index objects moving on the plane to efficiently answer range queries about their future positions. Our algorithms are based on previously described solutions as well as on the employment of efficient access methods. Finally, an experimental evaluation is included that shows the performance, scalability and efficiency of our methods. [Copyright &y& Elsevier]

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]