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

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

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

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.

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)

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