Single dimension search

[Andrew Leung]

Thanks for the help Paul. I will look at this approach.

Can you give me some idea of how poorly kd-trees will perform on single 
dimension queries, relative to k dimension queries? Will performance 
improve for 2 or 3 dimension queries?

The reason I am looking at using kd-trees is because I need to build an 
index over 6 or so dimensions, which will hold ~200,000 records. The 
index will be read-only after it is built. Queries over the index may 
query any combination of dimensions. Due to the highly skewed nature of 
the data, relational databases do not perform well enough. Are there 
better structures for this type of usage than kd-trees? Thanks.

Andrew


Paul Harris wrote:
> Hi Andrew,
>
> You might like to try visit_within_range().  You can write a visitor
> that tests whatever you want and then do whatever you want.   So you
> could test each point (within a 3d sphere range) against your 1
> dimension test and then do something with that point.
>
> But, you should keep in mind that kd-trees are not efficient for
> searching in one dimension.  If you want to find stuff in one
> dimension, then a set, a sorted vector, or boost's multi_index might
> be a better solution.
>
> kd-trees would be appropriate if you wanted to look through a set of
> nodes within a sphere of 3d space. (or a hypersphere of k-d space).
> that means a limited search area based on all of the dimensions, not
> just one.
>
> cheers,
> Paul
>
> On 19/01/2008, Andrew Leung <anwleung at gmail.com> wrote:
>   
>> Thanks for the quick reply.
>>
>> Now that I have changed the triplet '==' operator, how can I view all
>> matches from a find or find_nearest, which match the input triplet? The
>> only function that seems to have an output iterator for returned results
>> is find_within_range. If find or find_nearest have multiple points to
>> return, how can I retrieve these?
>>
>> Thanks again for your help.
>>
>> Andrew
>>
>> martin f krafft wrote:
>>     
>>> also sprach Andrew Leung <anwleung at gmail.com> [2008.01.18.2005 +0100]:
>>>
>>>       
>>>> For example, test_kdtree.cpp creates triplets and searches the tree
>>>> using other triplets as comparators. Is there a way I can search using 1
>>>> or 2 of the triplet fields, not all three? Such as, find all triplets
>>>> with a first dimension value of 5. Thanks for your help.
>>>>
>>>>         
>>> Kd-Trees are not made for this sort of search, but since you get to
>>> specify your own comparator, it's simple to do, I'd say:
>>>
>>> Modifying test_kdtree.cpp:
>>>
>>> inline bool operator==(triplet const& A, triplet const& B) {
>>>   return A.d[0] == B.d[0];
>>> }
>>>
>>>
>>> ------------------------------------------------------------------------
>>>
>>> _______________________________________________
>>> libkdtree-devel mailing list
>>> libkdtree-devel at lists.alioth.debian.org
>>> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>>>
>>>       
>> _______________________________________________
>> libkdtree-devel mailing list
>> libkdtree-devel at lists.alioth.debian.org
>> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>>
>>     
>
> _______________________________________________
> libkdtree-devel mailing list
> libkdtree-devel at lists.alioth.debian.org
> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
>
>