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:

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!

Håvard Tveite, Department of Mathematical Sciences and Technology, Universitet for Miljø- og Biovitenskap.

Valid HTML 4.01!