In this work an R-tree variant, which uses minimum
volume covering ellipsoids instead of usual minimum
bounding rectangles, is presented. The most significant aspects, which determine R-tree index structure
performance, is an amount of dead space coverage and
overlaps among the covering regions. Intuitively, ellipsoid 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 focus is put on the algorithm of ellipsoids construction
as it significantly affects indexing speed and querying
performance. At the end, the eR-tree undergoes experiments with both synthetic and real datasets. It
proves its superiority especially on clustered sparse
datasets. |
| Cite as: Danko, O. and Skopal, T. (2009). Elliptic Indexing of Multidimensional Databases. In Proc. Twentieth Australasian Database Conference (ADC 2009), Wellington, New Zealand. CRPIT, 92. Bouguettaya, A. and Lin, X., Eds. ACS. 87-95. |
 (from crpit.com)
(local if available)
|