Re: [Boost-users] can not compile nearest neighbors in d dimensions

Subject: Re: [Boost-users] can not compile nearest neighbors in d dimensions
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-04-16 09:49:48

Georgios Samaras wrote:
> Thanks for the replies, now it is clearer. However, the minimum 
> dimension I have in my datasets is 100 and I want to run NN with 
> dimension 10000.
>
> So, how I am going to initialize a point?
>
> template <int CompileTimeDimension>
> void fill(point& tmp)
> {
>     for(int j = CompileTimeDimension - 1 ; j >= 0 ; --j) {
>          bg::set<CompileTimeDimension-->(tmp, 5);
>      }
> }
>
> Even I can see that the above code won't even compile. Writting 
> manually bg::set<0>(tmp, 5), ..., bg::set<10000>(tmp, 5) does not 
> really sound a good idea. So what should I do?
>
> Maybe boost nearest's neighbors are meant to be used in higher dimensions?

I'm curious about the result! I didn't test Boost.Geometry for such big 
dimensions. One point will take 40kB, right? 1M of points would require 
40 GB of memory. I'm wondering how big will be the difference in 
performance of e.g. simple searching in std::vector in O(N) vs rtree 
kNN. How many points do you want to store in the rtree? If the number is 
too small you may not see the difference.

In order to handle arbitrary dimensions (more or less) you might replace 
the for-loop with the compile-time recursive template (see the code 
below). Assuming the compiler would be able to compile it (it will take 
some time).
E.g. VS2010 stops on CompileTimeDimension=3030 with the "error C1001: An 
internal error has occurred in the compiler" and a note: "compiler is 
out of heap space". It probably would be possible to somehow increase it 
with some compler parameter but I wouldn't recommend it.

So if you're sure that you're unable to specify some dimensions for 
which your program should work or at least make the possible range of 
dimensions shorter, e.g. you know that there can only be {100, 1000, 
10000} or at least [100, 200, 300, ... 10000], then Boost.Geometry is 
probably not suitable for you needs. Or maybe someone else has some 
other idea?

#include<boost/geometry.hpp>

#include  <boost/geometry/geometries/point.hpp>

#include  <boost/geometry/index/rtree.hpp>

namespace  bg  =  boost::geometry;

namespace  bgi  =  boost::geometry::index;

template  <int  CompileTimeDimension>

void  do_something()

{

     typedef  bg::model::point<float,  CompileTimeDimension,  bg::cs::cartesian>  point;

     bgi::rtree<point,  bgi::linear<8>  >  rt;

}

template  <int  CompileTimeDimension,  int  Max>

struct  do_something_for_dimension

{

     static  void  apply(int  run_time_dimension)

     {

         if  (  run_time_dimension  ==  CompileTimeDimension  )

             do_something<CompileTimeDimension>();

         else

             do_something_for_dimension<CompileTimeDimension  +  1,  Max>::apply(run_time_dimension);

     }

};

//  specialization  to  break  the  compile-time  recursion

template  <int  Max>

struct  do_something_for_dimension<Max,  Max>

{

     static  void  apply(int)

     {

         throw  std::runtime_error("run-time  dimension  not  found!");

     }

};

int  main()

{

     int  run_time_dimension  =  1000;

     if  (  run_time_dimension  <  100  ||  run_time_dimension  >=  10001  )

         std::cerr  <<  "invalid  dimension!";

     else

         do_something_for_dimension<100,  10001>::apply(run_time_dimension);

}

Regards,
Adam