CS542 Project Progress Report
Li Chen Ying Fua
October 27, 1997

Background

The R-Tree Structure

R-trees [1] are an extension of B-trees that store multi-dimensional data. R-trees are dynamically balanced. In most R-tree variant, entry MBRs are allowed to overlap. To improve this weakness, an R*-tree [11] is proposed that introduces heuristics in dynamic tree adjustment and yields a better query performance. R-trees are constructed in a bottom-up approach called the packed R-tree based on the Hilbert curve transformation [18]. The Hilbert value is used to partially sort the data and to pack them into tree nodes. As a result, the node occupancy rate is maximized whereas the overlap between entry MBRs is minimized.

About Bulk Incremental Update of R-tree

Perhaps the most critical issues in data warehouse environment is the time to generate and/or refresh its data index structure from the raw data, and the mere size of it does not permit frequent re-construction. Moreover, creating a new R-Tree index structure for new input spatial data sets from scratch is very wasteful. Hence, arise the issues on maintenance of R-Tree index structure efficiently whereby two postulates are made:

However, sorting could be the dominant cost factor in the above incremental computation. In addition, sorting multi-dimensional data ( especially spatial data object ) according to a predefined global ordering would impose too strong a limitation on the way spatial clustering can be achieved. Therefore, we are trying to find an approach on bulk incremental update which are solely based on standard routines for inserting, splitting and merging of R-trees.

Problem Definition

Our problem domain is defined as the bulk incremental update of R-Tree using newly input skewed data sets. This assumption has its reality basis: Using measurements on real data sets (road intersections of U.S. counties, star coordinates from NASA's Infrared-Ultraviolet Explorer etc.). We can provide evidence that real data are indeed skewed. Morever, since the original R-Tree has experienced many insertion and deletion operations on it, the newly input datasets would be more clustered than the data in the original R-Tree, at least in general cases.

Accomplished Tasks

Proposed Algorithm

Based on the problem definition, we come up with an idea of building a small R-Tree for the new input skewed data sets, then fit it into the original big R-Tree with some slight adjustment. By this way, we hope to achieve a good structured resultant R-Tree while preserving the natural clustering of the new input skewed data with minimum cost. Below is a rough description of the algorithm of how to fit a new small rtree into a big Rtree.

The height of small rtree is tex2html_wrap_inline86 ; the height of original rtree is tex2html_wrap_inline88 ; We consider the root rectangle of the small rtree ( enclosing rectangle of all new data rectangles ) as a data rectangle, and try to insert it to the level tex2html_wrap_inline90 of the original rtree, so the bottom level of the small rtree is on the same level as the original rtree.

ALGORITHM InsertSkewedDataset

ALGORITHM OverflowTreatment

ALGORITHM ReInsert

Since the small rtree is generally more skewed, clustered and packed, we do not want to decompose it into subtrees and fit them one at a time into the original rtree. Instead, we would like to use some methods ( described below ) to adjust other subtrees and keep the new rtree untouched.

(1)
Ideal Case
The most suitable level in the oiginal rtree for insertion of the small rtree has an entry slot for the root of the small rtree.

(2)
Merge Siblings
If there is no entry slot for the root of small rtree, we try to merge the sibling nodes in order to leave an entry slot for it.

Option 1
Merge between two closest nodes with relatively low capacity.

Option 2
Merge i+1 nodes into i nodes after sorting them by some hilbert value.

For Option 1 and 2, we can treat them as merging between multiple nodes. If the merge fails, that is the entries in i+1 nodes > max entries allowed in i nodes, redistribute them for some nodes to attract more entries.

Merging the (i+1) nodes, the tex2html_wrap_inline98 node would have the lowest capacity, so it could be deleted and re-insert from the root node.

Option 3
Select a candidate node with a relatively low capacity and perform a merge bottom-up, hoping that the resultant parent node would have very few children. In this case, we could delete it and make space for the small rtree, and re-insert its children from the root-node.

Comparisons between the 3 options

Overall, Option 3 might be too expensive and hence not so favorable.

(3)
Forced Re-insert
If no expected result is obtained in the merging step, we choose one sibling node to delete and re-insert, hoping to give way to the small rtree. We can choose the candidate sibling node by considering the distance between each children node from the center of its enclosing rectangle, and select the one that has the furthest distance.

(4)
Split
If all the above tries fail, split the parent node to create new entry slot for them.

Tasks At Hand

Weekly Schedule

Weekly Schedule
Week Tasks
1 Understand the packing code.
2-3 Implement simple structures and construct a simple R-tree.
4 Build up datasets and refinement/implementation of the proposed algorithm.
5 Implement the proposed algorithm and perform comparisons, if time permits.
6 Writeup of project report.

Appendix A

[1]
Antodgrsin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57

[2]
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31

[3]
Scott T. Leutenegger, J. M. Edgington, Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing. ICDE 1997: 497-506

[4]
Apostolos Papadopou dgrslos, Yannis Manolopoulos: Performance of Nearest Neighbor Queries in R-Trees. ICDT 1997: 394-408

[5]
Scott T. Leutenegger, Mario A. Lopez: A Buffer Model for Evaluating the Performance of R-Tree Packing Algorithms. SIGMETRICS 1996: 264-265

[6]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246

[7]
Vincent Ng, Tiko Kameda: Concurrent Access to R-Trees. SSD 1993: 142-161

[8]
Vincent Ng, Tiko Kameda: The R-Link Tree: A Recoverable Index Structure of Data. DEXA 1994: 163-172

[9]
Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145

[10]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246

[11]
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331

[12]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The R-File: An Efficient Access Structure for Proximity Queries. ICDE 1990: 372-379

[13]
Raymond T. Ng, Jiawei Han: Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994: 144-155

[14]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990

[15]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518

[16]
Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499

[17]
Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204

[18]
Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509

[19]
Christos Faloutsos, Ibrahim Kamel: High Performance R-trees. Data Engineering Bulletin 16(3): 28-33(1993)

[20]
Christos Faloutsos, Ibrahim Kamel: Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension. PODS 1994: 4-13

[21]
Yannis Theodoridis, Timos K. Sellis: Optimization Issues in R-tree Construction (Extended Abstract). IGIS 1994: 270-273

[22]
Vincent Ng, Tiko Kameda: The R-Link Tree: A Recoverable Index Structure for Spatial Data. DEXA 1994: 163-172

[23]
Dimitris Papadias, Yannis Theodoridis, Timos K. Sellis: The Retrieval of Direction Relations using R-trees. DEXA 1994: 173-182

[24]
Dimitris Papadias, Yannis Theodoridis, Timos K. Sellis, Max J. Egenhofer: Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees. SIGMOD Conference 1995: 92-103

[25]
Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573

[26]
Nick Roussopoulos, Yannis Kotidis, Mema Roussopoulos: Cubetree: Organization of and Bulk Incremental Updates on the Data Cube. SIGMOD Conference 1997: 89-99



Ah...bach!
Wed Oct 29 23:03:34 EST 1997