Re: [boost] Relational Template Library

From: Arkadiy Vertleyb (vertleyb_at_[hidden])
Date: 2005-10-11 08:40:03

"Jose" <jmalv04_at_[hidden]> wrote

> On 10/10/05, Arkadiy Vertleyb <vertleyb_at_[hidden]> wrote:
> >
> > "Jose" <jmalv04_at_[hidden]> wrote
> >
> > > I think it would also be useful to have RTL's basic distance example
> > shown
> > > in RML and then benchmark that with 10k+ points
> > [...]
> >
> (http://lists.boost.org/Archives/boost/2005/10/94890.php). All that needs
>
> > to be done is to complicate the condition, so that such things as merge
or
> > nested loops join are not possible. I think something like "abs(c1 - c2)
<
> > 1" should do fine. I already suggested this before.
>
>
> Can you explain "such tings as merge or nested loop joins are not
possible"
> ?

There are different ways to join tables.  In the example discussed both
tables are sorted the same way (it's actually the same table).  To join such
tables on the equal condition one can use merge, which is O(n+m) algorithm.
If the condition is more complicated, merge is not possible, and one has to
consider every possible combination (selection over cross-product), which is
a O(n*m) operation, and obviously, depending on the table size, orders of
magnitude slower.

BTW, the file you provided is very interesting.  I played with it yesturday,
but so far my results are pretty slow (no wonder -- I have to consider more
than 400,000,000 possible combinations).  One of possible reasons is the
lack of co-processor on my PC (quite a bit of math is done), but I also
found some RTL inefficiencies (as I said, we haven't spend a lot of time on
the optimization yet).  I will do some more research and then provide the
results.  Will probably take a few days to a week.

One thing that I also hope to show is that, even though the initial
calculations may be slow, the subsequent calculations on the updated table
will be very fast.

Regards,
Arkadiy