Stochastic Driven Relational R-Tree
Hans‐Peter Kriegel, Peter Kunath, Martin Pfeifle, Matthias Renz, Petra-Maria Strauß · Biblioteca Digital da Memória Científica do INPE (National Institute for Space Research) · 2003
Abstract. Modern spatial database applications including computer-aided design (CAD), medical imaging, molecular biology, or geographical information systems (GIS) impose new requirements on spatial query processing. Particular problems arise from the design goal to use general purpose database management systems in order to guarantee industrial-strength. Recently, there has been an increasing awareness that it is indispensable to integrate stand-alone spatial index structures, e.g. R-trees or Quadtrees, into fully-fledged database systems resulting in relational index structures, e.g. Relational R-trees or Relational Quadtrees. In this paper, we introduce stochastic heuristics for the Relational R-tree which are based on the fact that the Relational R-tree allows an individual fanout for each node. This freedom from minimal and maximal fill factors of nodes, offers a wide range of potential improvements. We develop algorithms that consider the quality of the entries of a node rather than just the quantity. Our experiments clearly demonstrate the advantages of this new stochastic driven Relational R-tree compared to the Relational R*-tree. 1