Test R-Tree Demonstration Java Applet - IMT, NMBU
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
- 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 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).
- 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).
- 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
// "standard" properies that can be read by
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.
- 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
- 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
- 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,
- Searching, deleting and adding is ignored during the split
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.
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).
BibTeX-entry (if you would like to reference
Comments, bug reports and suggestions are very welcome!
Department of Mathematical Sciences and
Norges miljø- og biovitenskapelige universitet.