Partial persistent index structures support efficient access to current and past versions of objects, while updates are allowed on the current version. The Multiversion B-Tree (MVBT) represents a partially persistent index-structure with both, asymptotic worst-case performance and excellent performance in real life applications. Updates are performed tuple-by-tuple with the same asymptotic performance as for standard B+trees. To the best of our knowledge, there is no efficient algorithm for bulk loading and bulk update of MVBT and other partially persistent index structures. In this paper, we propose the first loading algorithm for MVBT that meets the lower-bound of external sorting. In addition, our approach is also applicable to bulk updates. This is achieved by combining two basic technologies, weight balancing and buffer tree. Our extensive set of experiments confirm the theoretical findings: Our loading algorithm runs considerably faster than performing updates tuple-by-tuple.

Bulk-loading of R-trees has been an important problem in academia and industry for more than twenty years. Current algorithms create R-trees without any information about the expected query profile. However, query profiles are extremely useful for the design of efficient indexes. In this paper, we address this deficiency and present query-adaptive algorithms for building R-trees optimally designed for a given query profile. Since optimal R-tree loading is NP-hard (even without tuning the structure to a query profile), we provide efficient, easy to implement heuristics. Our sort-based algorithms for query-adaptive loading consist of two steps: First, sorting orders are identified resulting in better R-trees than those obtained from standard space-filling curves. Second, for a given sorting order, we propose a dynamic programming algorithm for generating R-trees in linear runtime. Our experimental results confirm that our algorithms generally create significantly better R-trees than the ones obtained from standard sort-based loading algorithms, even when the query profile is unknown.

Spatial histograms are extremely useful for approximate query processing in large spatial databases. The problem of generating optimal spatial histograms is NP-hard; therefore, many heuristic-based methods have emerged over the last 15 years. Shortcomings of these methods are their complex algorithmic design and their sensitivity to parameter setting, preventing them to be easily integrated into real systems. In this paper, we present a class of spatial histograms derived from the popular family of R-tree indexes. We propose a cost-optimized approach that combines bulk-loading of R-trees and the construction of spatial histograms. This results in a robust histogram method with high accuracy for selectivity estimation of spatial queries. Our method does not require the setting of intuitive parameters at all. In addition, the estimation error continuously decreases with increasing number of histogram buckets, and therefore, our histogram methods can take benefit from large main memories. In an experimental evaluation, we compare the performance of our histograms with state-of-the-art spatial histograms. Our results confirm that our histograms provide low estimation errors and short build-times.