Elliptic indexing of multidimensional databases
Ondrej Danko, Tomáš Skopal · 2009
In this work an R-tree variant, which uses minimum volume covering ellipsoids instead of usual minimum bounding rectangles, is presented. The most signifi-cant aspects, which determine R-tree index structure performance, is an amount of dead space coverage and overlaps among the covering regions. Intuitively, el-lipsoid as a quadratic surface should cover data more tightly, leading to less dead space coverage and less overlaps. Based on studies of many available R-tree variants (especially SR-tree), the eR-tree (ellipsoid R-tree) with ellipsoidal regions is proposed. The fo-cus is put on the algorithm of ellipsoids construction as it significantly affects indexing speed and querying performance. At the end, the eR-tree undergoes ex-periments with both synthetic and real datasets. It proves its superiority especially on clustered sparse datasets. 1