Test R-Tree Demonstration Java Applet - IMT, UMB

This implementation uses the algorithms outlined in the original paper on the R-Tree [Guttman 1984].
There is also a Norwegian language version of this WWW-page. Other languages can be supported by changing the parameters to the Java Applet.

More detailed information about the program and algortithms can be found in the on-line help. In the references you will also find a link to an on-line version of Guttmans original paper.

The following functionality is presently implemented:

• You can choose single tree mode or dual tree mode ("Dual mode"). Dual tree mode is useful for comparing the behaviour of different variants of branch factor and split algorithm. Animations are not affected by a switch between dual and single tree mode.
• You can choose node capacity ("branch factor") for the R-tree(s). You can specify "M" (the maximum number of entries that will fit in one node) and "m" (the minimum number of entries in a node) separatly. "m" has to be less than or equal to "M"/2! If you change node capacity while there is an animation going on, the animation will be stoppet, and the event sequence rerun to the current step.
• You can choose split algorithm(s) ("Linear cost splitting", "Quadratic cost splitting" or "Exhaustive splitting"). The "Exhaustive" method should only be used for small M (maximum 8-10, depending on your hardware). If you change splitting method while there is an animation going on, the animation will be stoppet, and event sequence will be rerun until the current step.
• You can search ("Search") for rectangles in the "interaction map" window and both the "tree" windows. The qualifying rectangles will be highlighted in both the "map" windows and the "tree" windows. Use the mouse to drag out a search region in the "map window" (all overlapping and touching rectangles are selected). In the "tree" windows, click on the node (internal node or leaf node) to select all of its children, or click on a leaf entry to select a single leaf entry.
• You can add new entries/rectangles ("Add rectangle") in the "map window" and study what happens to the R-Tree. Use the left mouse button to drag out a new rectangle. If you add a new entry in the middle of an animation sequence, the remaining events in the sequence will be discarded.
• You can delete entries/rectangles ("Delete rectangle(s)") from the "map window". Use the mouse to drag out the search region (all overlapping and touching entries / rectangles will be deleted). If you delete entries in the middle of an animation sequence, the remaining events in the sequence will be discarded.
• You can delete the complete R-Tree (use the "Clear"-button).
• You can get statistics on the tree(s) ("Tree statistics"). When the button is pressed, the tree height is returned, and one line for each level of the tree, containing:
  • The tree level (leaf = 1).
  • The brutto sum of the areas of the rectangles at this level.
  • The netto (counting overlapping areas only once) sum of the areas of the rectangles at this level.
  • The percentage of overlap between the rectangles.
  • A factor that shows the area compared to the area covered by the leaf entries (brutto areas).
  The output is written in a text area in the right part of the Applet (for dual trees, the output for the left R-Tree is written in a text area in the left part of the Applet).
• You can export and import R-trees using the "Export" and "Import" buttons. During export, the sequence of R-tree events (insertion of leaf nodes and deletion of leaf nodes) is shown in a text window, from where you for instance can copy it into a text file using cut and paste.
  Note: Oracle Java 6, update 24, will not allow cut and paste between the clipboard and an Applet without explicit permission. In order to be able to do cut and paste, one either has to switch to an older Java version or add the following line to the java.policy file (below the line
  // "standard" properies that can be read by anyone):
  permission java.awt.AWTPermission "accessClipboard";
  You can modify the content of the text window by deleting, typing or using cut and paste (see note above). When clicking "Import", the sequence of R-tree events (inserts and deletes) that are represented in the text window is used to build a new R-tree. You can not append R-tree leaf nodes using the import function, as the existing tree is always deleted before building the new R-tree.
• A "Help" button will bring up a WWW-page with more information about the Applet and the R-Tree implementation.
• When the cursor is in the main map window, its position (x,y) is shown near the bottom of the right part of the Applet. This can be useful during insertion if you have determined sizes and positions for the rectangles you are about to add.
• Animation.
  • You can choose the delay between each step in the animation ("Animation delay, ms:"). The value of 9999999 ms can be used to manually step through the animation.
  • It is possible to run a predefined "demo" (using the "Demo"-button). The R-Tree(s) will be deleted, and then a set of predefined rectangles are inserted into the new tree(s). After on you can continue insert or delete rectangles manually.
  • You can "replay" the R-Tree(s) (using the "Rerun"-button). This means that the R-Tree is first deleted, and then all R-Tree events (insertions and deletions of leaf nodes) are replayed in their original sequence. This means that it is for instance possible to change the node capacity or node splitting algorithm and see what effect this has on the resulting tree structure.
  • You can use the "Next"-button to step forward through the animation.
  • You can use the "Back"-button to step backwards in the animation.
  • During animations, the next event is indicated in the map window with a highlighted non-filled rectangle of the next R-Tree leaf node to be inserted or deleted (using a cross to indicate deletion).
• Node split visualisation / animation (for the linear and quadratic cost split algorithms)
  • You can investigate the behaviour of the splitting algorithms by choosing the "Split focus" mode, and clicking the node you are interested in in the tree structure window. The node is then highlighted in the map and the tree.
  • When the focus node overflows, the split animation is visualised in steps: First, the entries are shown with numbers corresponding to their position among the entries, then the two seeds are highlighted, then the distribution of the remaining entries is shown step by step.
  • During the visualisation, the entries in the nodes are numbered on the map, according to their sequence in the node (this is important for the "Linear cost splitting" algorithm).
  • The "Next" and "Back" buttons can be used to move forward or backward in the animation.
  • Animation delay can be changed during the animation. The value of 9999999 ms can be used to manually step through the animation.
  • The visualisation will be aborted if the split algorithm or node capacity is changed, if there is a change from single to dual mode or vice versa, or if any of the following buttons are activated: clear tree, import tree, export tree, tree statistics, run demo, rerun.
  • Searching, deleting and adding is ignored during the split visualisation.

At the moment, three node splitting algorithms are implemented. They are the original "quadratic cost" and "linear cost" algorithms specified by Guttman [Guttman 1984], and also an exhaustive split algorithm (not specified directly by Guttman). The exhaustive split algorithm will take a very long time for large node sizes.

Reinsertion after deletion is done in accordance with CT6 in Guttman's algorithm "CondenseTree", which states that "higher level nodes must be placed higher in the tree...". We have chosen to reinsert the upper level nodes first and the leaf nodes last.

References

Antonin Guttman. "R-Trees: A Dynamic Index Structure for Spatial Searching". Proceedings, ACM SIGMOD'84, Boston, MA, June 18-21 1984, pp. 47-57 (PDF).

R-Tree@DB&LP

BibTeX-entry (if you would like to reference it)

Comments, bug reports and suggestions are very welcome!