Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
Solved

# R-Tree

Posted on 1999-07-29
Medium Priority
455 Views
Can anyone give me the source code for R-Tree and R*-Tree?
And description on how to use them.
0
Question by:rafiq99
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 4
• 3

LVL 3

Accepted Solution

Laminamia063099 earned 1200 total points
ID: 1201324
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:
http://gist.cs.berkeley.edu:8000/gist/libgist/libtour.html,
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.

Laminamia

"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."

0

LVL 3

Expert Comment

ID: 1201325
Are you working with GIS?

Laminamia
0

Author Comment

ID: 1201326
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......

0

Author Comment

ID: 1201327
I'm using DTM data for visualization
0

LVL 3

Expert Comment

ID: 1201328
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.

http://www.students.uiuc.edu/~pjain/user_doc1.html

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 :)
0

Author Comment

ID: 1201329
Hi,
I manage to find a version of Rtree that work with VS6.0. but the coding is in C.
U can find it from
http://www.superliminal.com/sources/sources.htm

Thankx for ur help.
:)

0

LVL 3

Expert Comment

ID: 1201330
Good luck!
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. Aâ€¦
Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and â€¦
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
###### Suggested Courses
Course of the Month7 days, 11 hours left to enroll