Can anyone give me the source code for R-Tree and R*-Tree?
And description on how to use them.
Who is Participating?
Laminamia063099Connect With a Mentor Commented:
Here is some fairly informative information on the R-Tree and the R*Tree.  It sounds like you already know something about them, but I include this because it comes from the site which has a library implementing the R-tree and the R*tree.  Look at:
and the source is found at:
in both zip and tar form.

I would include information on how to use these libraries, but it is contained at the same place as the first hypertext link. (libtour.html)  I hope this will help you in your work! and if you have any questions, please ask and I'll try to answer them.


"R-trees were first proposed by Guttman [Gut84] to index geographic data (points, lines, and polygons), in order to efficiently find data that satisfy geographic predicates (i.e., key {contains,contained-in,overlaps,equals} constant). The keys in a (2D) R-tree are "bounding boxes", i.e. rectangles which are aligned with the x and y axes. A key signifies that all objects stored below it fall within that geographic area. If you want more detail on R-trees, Guttman's paper makes for fairly accessible reading.

The R*-tree is very much like the R-tree, having identical keys and supporting identical query predicates. But it contains some optimizations that often make t outperform simple R-trees during lookup, by paying for some additional complexity during insertion. First, it has different Penalty and PickSplit methods. Second, it uses a technique known as Forced Reinsert to keep the tree fuller and better balanced than an R-tree.

Forced reinsert works as follows -- when an entry is inserted into a full node, some percentage of the entries on that node are deleted, and reinserted into the tree. If the node is at a non-leaf level, the reinsertion places the deleted entries back into nodes at that level.  If reinsertion discovers a full node, then it splits it as usual. This sporadic reinsertion of elements accomodates changes in the data distribution as the tree fills in."

Are you working with GIS?

rafiq99Author Commented:
Hi Laminamia, thankx for answering .
Actually I have tried to work on GIST b4 this n still am.
I actually got their version 1.0, the one u give me was version 0.9b.
U can get it from http://gist.cs.berkeley.edu/libgistv1/
 My prob., is that I cannot make in  
\libgist\src\make.bat because the Bison/Flex I'm using is for Microsoft Developer studio 97. I'm using Visual Studio 6.0, don't  have MDS 97.
Did u manage to run the prog? If u did can u give me a version that work with VS6.0?

Thanx again......

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

rafiq99Author Commented:
I'm using DTM data for visualization
Hmmm.  I don't think I'll be able to help there.  You'll probably need to use MDS 97 to have it work with your Bison & Flex. :(  

The only thing I can think of is to try this module created by some grad students at the University of Illinois.  


It's a .tar.gz file, so you'll need to extract it through Unix, but it should be able to be compiled on any OS.  Sorry I couldn't tell you anything that you haven't already tried.

Laminamia :)
rafiq99Author Commented:
I manage to find a version of Rtree that work with VS6.0. but the coding is in C.
U can find it from

Thankx for ur help.

Good luck!
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.