Visit_within_range predicate

[Paul Harris]

Hi Andrew,

Uuuh, then you should make a kdtree with just 3 dimensions?

Otherwise if you make a 12 dimension tree, then yes the order may help a
little, but only if your tree is very shallow (ie not many nodes).

Otherwise it will have to cycle through the other 9 dimensions quite often.

I would suggest for performance, you have a 'general' tree that can handle
all the dimensions (at a cost), and then other trees that are tailored to
your most-used subset of dimensions.

If each node is small, then it'll be ok to have multiple copies of the nodes
(depending on your needs), but if the node is large, or some sort of 'active
object'... then store those nodes outside the tree, and store
pointers/handles/iterators/indexes in the tree.

For some of my trees, I don't store the actual node in the tree.  Instead I
create a vector to store the data, and build the trees with pointers to the
data.  I write the accessors so they know how to access through a pointer.

The trick with that is your vector must never resize or erase or insert (and
thus invalidate all the pointers).

Other alternatives including using boost::smart_ptr<> as pointers, or using
an std::list (only invalidates an interator if you erase it), or a
vector+indexes (accessors must have a pointer to the vector).   That all
comes down to data management and depends entirely on your app, how often
the data is changed, the nature of the data, etc.  You would need to think
about the "pointer" and when it would get invalidated.

If you change your dataset, you'd also have to adjust your tree.  It might
be easier to just rebuild the tree(s) each time, if the dataset doesn't
change much.

see ya
Paul


2009/8/24 Andrew Leung <anwleung at gmail.com>

> Hi,
>
> Thanks for the quick response.
>
> Another quick question. Most of the range queries I perform use the same 3
> dimensions. Each node has 12 total dimensions. For performance, does it
> matter where in the dimension order these 3 dimensions should be? If they
> are the first 3 dimension checked it seems like performance would be
> improved, especially since I stop searching after the first match. Thanks.
>
> Andrew
>
> On Aug 22, 2009, at 7:55 PM, Paul Harris wrote:
>
> the find_ and visit_ methods either will find the 'nearest', or find 'all'
> in the range...
> So without writing a new method called something like
> visit_first_within_range(), you could just throw an exception inside the
> visitor when you have a satisfactory result.
>
> eg
>
> struct found_one
> {
>    YourInfo info;
> };
>
> class Visitor
> {
>    etc operator() etc
>   {
>     found_one result;  result.info = whatever;  throw result;
>   }
> }
>
> then a try, catch block will catch the results.
>
> Sorry thats a bit messy, but thats one approach.
>
> Paul
>
>
> 2009/8/23 Andrew Leung <anwleung at gmail.com>
>
>> Hi,
>>
>> I am using libkdtree++ and would like to get a couple of tips on how I can
>> improve my performance.
>>
>> In most instances when I query the KD-tree using the visit_within_range()
>> function, I do not need to continue the search once any tree node is found
>> that is within the range. Is there a way to stop the query once a node is
>> found to satisfy the query? The REGION.encloses() call tends to be very
>> expensive and I would like to avoid any needless calls to this function. Is
>> it possible to just 'return visitor;' when the REGION.encloses() condition
>> is meet?
>>
>> Thanks.
>> Andrew
>>
>> _______________________________________________
>> libkdtree-devel mailing list
>> libkdtree-devel at lists.alioth.debian.org
>> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20090824/be4a2863/attachment.htm>