Approximate Nearest Neighbors (NN) Libraries in high-dimensions | FLANN vs CGAL vs BOOST

NN (FLANN,CGAL,BOOST)

In this article, I will share with you my experience with FLANN, CGAL and BOOST libraries in (approximate) Nearest Neighbor (NN) Searching.

First thing to do is installing the library. BOOST was the easier since it didn’t need compilation for our purposes. FLANN was easy too, with specific installation steps found in the manual. CGAL, was the hardest, but remember CGAL is huge (it covers many things in computational geometry).

For installing the first two, just reffer to their website. For CGAL do that too, but this installation for CGAL in Linux may be helpful too (it has steps for installing Linux too).

Once you install the library, comes the documentation and how clean the interface is. FLANN was the best, since it is small, robust and even if something isn’t clear in the documentation, you can easily find it in the code files. One disadvantage, is that the dataset must (at least from my perspective) be stored in a 2D array, but I use C++ for this purpose, so an std::vector would be nice.

CGAL, has good documentation, but you need to get familiarize with its concepts. Once you do that, you will be ok, but takes more effort than in FLANN.

BOOST was a failure. Remember, that we are exploring these libraries for high dimensions. It provides interface only for 2 and 3 dimensions. Moreover, you can not have your code accept any dimension the use wants (!), but you must limit the user to choose only some pre-defined (!) dimensions.

Just to define a point in d dimensions, I would need to write a recursive function, style that reminds me of Prolog. Moreover, the point had all the values initialized to the same value, not so realistic scenario. Just take a look at the code:

template <std::size_t D, std::size_t N>
struct fill
{
    template <typename Point>
    static void apply(Point& p, typename bg::coordinate_type<Point>::type const& v)
    {
        bg::set<D>(p, v);
        fill<D + 1, N>::apply(p, v);
    }
};
template <std::size_t N>
struct fill<N, N>
{
    template <typename Point>
    static void apply(Point&, typename bg::coordinate_type<Point>::type const&) {}
};

We should also compile it with a special option. Just to use 100 and 10000 dimensions, I had to write this: “c++ -I ../ bla.cpp -std=c++0x -ftemplate-depth-170001 -o bla”. That’s the reason you can’t have the user choose its dimension (because the depth of the compilation is limited). Further effort made me say: “Use BOOST only in 2D or 3D, not in higher dimensions.”

However, the main criterion is performance. It was clear, that FLANN outperformed CGAL in higher dimensions, since in experiments performed in 17D, CGAL already started loosing its efficieny over linear search. I tested FLANN on 100 and 10000 dimensions and the speedup was significant (but you find – usually – an approximation of the true NN).

CONCLUSION: FLANN wins CGAL and BOOST in high dimensions.

Non-programmer using Linux

Linux & people

The other day, at Cage, where we play football and I a guy from the field of Economics, asked me what I think about Linux. I answered back, with excess confidence, that Linux is not for people, it’s for programmers. Was I wrong? Mr. P. Kokkoris, a guy from Psychology field had installed Linux on his laptop and that was a surprise to me. So, I made him some questions…

Since some people asked me, I included a step by step guid for a dual boot with windows7 and Linux here. Alternatively, you can look at the comments sections.

How did you learn about Linux? Most people are not aware of this OS.

My neighbor installed them at his laptop, because he had been bored of Windows xp. Moreover, he was not able to reinstall Windows as easily as Ubuntu…I spotted them, he told me that they are fast and light and I thought, perfect, because I have an old laptop that needs a boost!
How did you install Linux? Was it easy or not?

Advices on the official site are so accurate, that even an Orang could succeed in this installation!
What do you adore in Linux?

I like the ease of the installation with multiple ways. I adore that I have all the apps installed, the ones that I would have to install by my own in Windows. For example, I did not have to install mtorrent, winrar. The most significant issue, is that these programs for opening a pdf and related tasks are way better that the ones of microsoft office.
What do you miss from Windows?

There are times that Linux are unbearable and even Google can not provide a solution, because I am doomed to use a stupid thing (probably he means the terminal), where I need to give commands in programming languages..On these situations, I am completely lost.
Are you happy from your desicion? Would you suggest Linux to ohters too?

I am not changing Ubuntu for nothing…I unreservedly recommend them on simple users like me, regardless of the rumors that want Linux to be for advanced users. That’s all folks, hope I helped the progress of science.

I would like to thank Mr. Kokkoris for answering these questions. I would also like to thank him for making me think of something. Should I also use Linux for my “simple user” tasks?

Erasmus

Erasmus

 NEW!  Erasmus announced for DIT here.

On the winter semester of 2012, I , G. Samaras was transferred from DIT, Athens to USI, Switzerland, via Erasmus program. There is no doubt, that this was a lifetime and unique experience, that I suggest everybody that has the privilege, to go for it!

Despite the fact that I have traveled in many countries before, Erasmus gave me the opportunity to meet people from other countries as a student, and not as tourist. I made friends from other countries, without of course forgetting the ones at home ;), I saw how other cultures interpret situations and life moments. Most of the things in life are relevant and some nations see things different from other nations. However, the more strong globalization becomes, the less obvious these differences become! And I saw how people from other countries deal with their every day life, with their work, their projects, the parties, the football (played with some very good players and with Italian defenders!) and everything else you can imagine. At this point, I would like to state, that, objectively, Greek people are in the top clean nations, based on the way they treat their homes.

From a technical aspect, I had the unique-in my mind- opportunity, to program a robot, to learn web technologies that have not yet been introduced in Greece (!), (see also this post). Moreover, I was introduced and used the powerful CGAL library in the course of Algorithms. I saw in which programming paradigm the foreign programmers are strong and in which they are weak. Also, I realized how much Greek words and symbols are used in science! Finally, I get used to speak with English terms, something that I would say, is essential for someone who studies informatics and telecommunications.

You also learn to adopt in new situations and leave away from home. However, the best part is for sure the one that I have not yet leave. The return at home after many months!! As one guy from Κλουβί stated, this is going to be a celebration!

We have created some pages, in which we wrote our experience from Erasmus.

What is that?

What is that?

||
       ||
   ||
||
||
||
V

Did you watch the video?

No     Yes

||
       ||
   ||
||
||
||
||
||
||
||
||
||
||
||
V

You might be lost in thousands line of code right now (or in your studies, your work, your thoughts, etc.), but take a break, call your parents to say how much you love them…

Post dedicated to my family, which I miss and love very much!