www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - R-Tree

reply =?UTF-8?B?Ikx1w61z?= Marques" <luis luismarques.eu> writes:
Has any of you ever implemented an R-Tree in D? Do you have code 
/ experience to share?
Oct 22 2013
parent reply "Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
On Tuesday, 22 October 2013 at 17:41:20 UTC, Luís Marques wrote:

 Has any of you ever implemented an R-Tree in D? Do you have 
 code / experience to share?


I have at least partially implemented in C++ before.  I have good
news and bad news on that.  The bad news is I can't find my code
anywhere, but that is also the good news - because it was
undoubtedly an absolute mess.

If you haven't already found it the following book was useful
(nasty link but seems to work).

http://www.google.ca/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC0QFjAA&url=http%3A%2F%2Fdelab.csd.auth.gr%2Fpapers%2FTRSurveyRtree03_mnpt.pdf&ei=JMBmUon_KOLV2AXqsICwAw&usg=AFQjCNFrqHx1q4QwjgoBC2fs2XLSo2_QlQ&sig2=nSA5SUQRL56pub2FyQ80iA&bvm=bv.55123115,d.b2I

Is this something you plan to make publicly available at some
point.  If so I would be interested in helping out.

Craig
Oct 22 2013
parent reply "Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
On Tuesday, 22 October 2013 at 18:20:07 UTC, Craig Dillabaugh
wrote:

 On Tuesday, 22 October 2013 at 17:41:20 UTC, Luís Marques wrote:

 Has any of you ever implemented an R-Tree in D? Do you have 
 code / experience to share?


 I have at least partially implemented in C++ before.  I have 
 good
 news and bad news on that.  The bad news is I can't find my code
 anywhere, but that is also the good news - because it was
 undoubtedly an absolute mess.

 If you haven't already found it the following book was useful
 (nasty link but seems to work).

 http://www.google.ca/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CC0QFjAA&url=http%3A%2F%2Fdelab.csd.auth.gr%2Fpapers%2FTRSurveyRtree03_mnpt.pdf&ei=JMBmUon_KOLV2AXqsICwAw&usg=AFQjCNFrqHx1q4QwjgoBC2fs2XLSo2_QlQ&sig2=nSA5SUQRL56pub2FyQ80iA&bvm=bv.55123115,d.b2I

 Is this something you plan to make publicly available at some
 point.  If so I would be interested in helping out.

 Craig


Sadly for me, I was able to find it. Its a bit embarrassing but
the code can be found here in all its undocumented glory.  Likely
not state-of-the-art.

http://cg.scs.carleton.ca/~cdillaba/comp5409_project/code/index.html

Note, this was sort of an experimental R-tree, trying to test an
idea I was working with on performing bulk queries in external
memory.  So are some extra's in there.  I gave up on the idea
shortly thereafter - so that likely indicative of the quality of
the concept ...  anyway it might help you understand the code:

http://cg.scs.carleton.ca/~cdillaba/comp5409_project/BatchSearch.html

Craig
Oct 22 2013
parent reply "Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
On Tuesday, 22 October 2013 at 18:53:32 UTC, Craig Dillabaugh
wrote:
clip

 Sadly for me, I was able to find it. Its a bit embarrassing but
 the code can be found here in all its undocumented glory.  
 Likely
 not state-of-the-art.

 http://cg.scs.carleton.ca/~cdillaba/comp5409_project/code/index.html

 Note, this was sort of an experimental R-tree, trying to test an
 idea I was working with on performing bulk queries in external
 memory.  So are some extra's in there.  I gave up on the idea
 shortly thereafter - so that likely indicative of the quality of
 the concept ...  anyway it might help you understand the code:

 http://cg.scs.carleton.ca/~cdillaba/comp5409_project/BatchSearch.html

 Craig


If you look at the code in rect.h/rect.cpp there is code for
generating Hilbert values for the rectangles (that I can't
personally take credit for).  It is sort of useful for
constructing balanced R-trees.
Oct 22 2013
parent reply =?UTF-8?B?Ikx1w61z?= Marques" <luis luismarques.eu> writes:
Thanks Craig, I will look into this and give you feedback when 
possible :-) (this is lower priority than some of my other active 
threads, right now)
Oct 23 2013
parent "Craig Dillabaugh" <cdillaba cg.scs.carleton.ca> writes:
On Wednesday, 23 October 2013 at 14:30:09 UTC, Luís Marques wrote:

 Thanks Craig, I will look into this and give you feedback when 
 possible :-) (this is lower priority than some of my other 
 active threads, right now)


Hope it is helpful.  My code isn't likely the best guide at this
was one of my first efforts ever at coding a non-trivial data
structure.  The Hilbert stuff is hopefully useful though, as it
makes the process of construction (which is really the only
technically challenging part) straightforward.  Apart from
construction R-Trees are pretty simple structures.

Cheers,

Craig
Oct 23 2013