[GRASS5] lib/vector/rtree/split_l.[c|h]

Radim Blazek radim.blazek at gmail.com
Mon Aug 22 08:51:42 EDT 2005


On 8/22/05, Brad Douglas <rez at touchofmadness.com> wrote:
> On Mon, 2005-08-22 at 12:00 +0200, Radim Blazek wrote:
> > On 8/21/05, Markus Neteler <neteler at itc.it> wrote:
> > > On Sat, Aug 20, 2005 at 11:25:31PM -0700, Brad Douglas wrote:
> > > > Is it okay if I remove split_l.[c|h] from lib/vector/rtree and it's
> > > > Makefile?  They are unused and essentially duplicated in split_q.[c|h].
> > > >
> > > > IMHO, it's clutter that serves as obfuscation.
> > > >
> > >
> > > It should be ok (and it doesn't get lost in CVS).
> > >
> > > Markus
> >
> > I would prefer to keep it in CVS,  split_l and split_q implement 2 methods
> > for node splitting and I had not time to think/test both in GRASS.
> > If we leave it there, hopefully someone can compare both with real data.
> > Look also in MAILS:
> >
> > | regarding split_l.c vs. split_q.c: these involve a choice you can make between
> > | speed and box optimization. you should use the quadratic version ('q') if it's
> > | fast enough for your needs, and use the less expensive linear method
> > if not. note
> > | that in both cases various branches of the resulting rectangle trees
> > may overlap.
> > | there's another version of the technique called "R+ Trees" which guarantees no
> > | overlaps, but i don't have an implementation of that version. i
> > believe it's even
> > | slower than either r-tree splitting method, so you should probably
> > also take all
> > | of that into account.
> 
> I saw that in MAILS, but I was under the assumption that computers were
> now sufficiently fast as not to generate much overhead.  It has been
> three years since MAILS was authored.
> 
> Do we have timing differences between the two methods?  How much extra
> overhead are we talking?  Seconds?  Minutes?
> 
> Can we make this an option in the configure script to define a wrapper
> macro?  As of now, few people knows the different methods exist and even
> fewer are going to do the nasty coding to make them work.
> 
> I have already deleted them, but they can be easily brought back.  I
> would just like to have a good reason to do so.

OK. 

Notes on spatial index:
There are problems with space occupied by spatial index but I don't 
know how much it depends on splitting method used.
It would be also interesting to experiment with MAXCARD.
Also dimension should be changed dynamicaly (currently 3D).

Radim




More information about the grass-dev mailing list