โ Scribed by Beckmann, Norbert; Seeger, Bernhard
No coin nor oath required. For personal study only.
In this paper we present an improved redesign of the R*-tree that is entirely suitable for running within a DBMS. Most importantly, an insertion is guaranteed to be restricted to a single path because re-insertion could be abandoned. We re-engineered both, subtree choice and split algorithm, to be more robust against specific data distributions and insertion orders, as well as peculiarities often found in real multidimensional data sets. This comes along with a substantial reduction in CPU-time.
Our experimental setup covers a wide range of different artificial and real data sets. The experimental comparison shows that the search performance of our revised R*-tree is superior to that of its three most important competitors. In comparison to its predecessor, the original R*-tree, the creation of a tree is substantially faster, while the I/O cost required for processing queries is improved by more than 30% on average for two-and three-dimensional data. For higher dimensional data, particularly for real data sets, much larger improvements are achieved.
๐ SIMILAR VOLUMES
Join ordering is one of the most important, but also most challenging problems of query optimization. In general finding the optimal join order is NP-hard. Existing dynamic programming algorithms exhibit exponential runtime even for the restricted, but highly relevant class of star joins. Therefore,