Debian Bug report logs - #652103
RFP: nanoflann -- C++ header-only fork of the FLANN library for KD-trees

Package: wnpp; Maintainer for wnpp is wnpp@debian.org;

Reported by: "Jose Luis Blanco \(University of Malaga\)" <joseluisblancoc@gmail.com>

Date: Wed, 14 Dec 2011 20:03:02 UTC

Severity: wishlist

Reply or subscribe to this bug.

Toggle useless messages

View this report as an mbox folder, status mbox, maintainer mbox


Report forwarded to debian-bugs-dist@lists.debian.org, debian-devel@lists.debian.org, debian-science%40lists.debian.org, debian-science@lists.debian.org, joseluisblancoc@gmail.com, wnpp@debian.org, "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>:
Bug#652103; Package wnpp. (Wed, 14 Dec 2011 20:03:05 GMT) Full text and rfc822 format available.

Acknowledgement sent to "Jose Luis Blanco \(University of Malaga\)" <joseluisblancoc@gmail.com>:
New Bug report received and forwarded. Copy sent to debian-devel@lists.debian.org, debian-science%40lists.debian.org, debian-science@lists.debian.org, joseluisblancoc@gmail.com, wnpp@debian.org, "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>. (Wed, 14 Dec 2011 20:03:05 GMT) Full text and rfc822 format available.

Message #5 received at submit@bugs.debian.org (full text, mbox):

From: "Jose Luis Blanco \(University of Malaga\)" <joseluisblancoc@gmail.com>
To: Debian Bug Tracking System <submit@bugs.debian.org>
Subject: ITP: nanoflann -- C++ header-only fork of the FLANN library for KD-trees
Date: Wed, 14 Dec 2011 20:59:12 +0100
Package: wnpp
Severity: wishlist
Owner: "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>

* Package name    : nanoflann
  Version         : 1.1.0
  Upstream Author : Jose Luis Blanco Claraco <joseluisblancoc@gmail.com>
* URL             : http://code.google.com/p/nanoflann/
* License         : BSD
  Programming Lang: C++
  Description     : C++ header-only fork of the FLANN library for KD-trees

nanoflann is a C++ header-only library for building KD-Trees, mostly optimized 
for 2D or 3D point clouds. Queries for neighbors around any arbitrary location 
in space can then be solved quickly and efficiently using Approximate Nearest 
Neighbor (ANN) algorithms.

This implementation is roughly one order of magnitude faster than some other 
popular KD-tree libraries.

nanoflann does not require compiling or installing any binary library, just 
an #include <nanoflann.hpp> in your code.

This library is a fork (and a subset) of the `flann` library, by Marius Muja 
and David G. Lowe, which was started by Jose Luis Blanco Claraco. Following 
the original license terms, nanoflann is distributed under the BSD license.




Information forwarded to debian-bugs-dist@lists.debian.org, wnpp@debian.org, "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>:
Bug#652103; Package wnpp. (Wed, 14 Dec 2011 20:45:05 GMT) Full text and rfc822 format available.

Acknowledgement sent to martin f krafft <madduck@debian.org>:
Extra info received and forwarded to list. Copy sent to wnpp@debian.org, "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>. (Wed, 14 Dec 2011 20:45:05 GMT) Full text and rfc822 format available.

Message #10 received at 652103@bugs.debian.org (full text, mbox):

From: martin f krafft <madduck@debian.org>
To: "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>, 652103@bugs.debian.org
Subject: Re: Bug#652103: ITP: nanoflann -- C++ header-only fork of the FLANN library for KD-trees
Date: Wed, 14 Dec 2011 21:40:59 +0100
[Message part 1 (text/plain, inline)]
also sprach Jose Luis Blanco (University of Malaga) <joseluisblancoc@gmail.com> [2011.12.14.2059 +0100]:
> nanoflann is a C++ header-only library for building KD-Trees,
> mostly optimized for 2D or 3D point clouds.

I won't ask what "clouds" are, but please tell us about how the
2D/3D optimisation happens.

> This implementation is roughly one order of magnitude faster than
> some other popular KD-tree libraries.

What are other popular KD-tree libraries? And does this apply to
2D/3D only?

How does nanoflann compare to libkdtree++? Why would you want to use
one over the other?

Note: I am the author of libkdtree++, and I think choice is good.
However, I simply don't believe some of the claims made in the long
description, and I question the usefulness of 2D/3D optimisation wrt
KD-Trees: if you are dealing with only two or three dimensions,
KD-Trees are usually not what you want. Then again, that was just my
experience, my KD-Trees usually had dimensions in the low thousands…

-- 
 .''`.   martin f. krafft <madduck@d.o>      Related projects:
: :'  :  proud Debian developer               http://debiansystem.info
`. `'`   http://people.debian.org/~madduck    http://vcs-pkg.org
  `-  Debian - when you have better things to do than fixing systems
 
philosophy: unintelligible answers to insoluble problems.
[digital_signature_gpg.asc (application/pgp-signature, inline)]

Information forwarded to debian-bugs-dist@lists.debian.org, wnpp@debian.org, "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>:
Bug#652103; Package wnpp. (Wed, 14 Dec 2011 21:27:09 GMT) Full text and rfc822 format available.

Acknowledgement sent to Jose Luis Blanco <joseluisblancoc@gmail.com>:
Extra info received and forwarded to list. Copy sent to wnpp@debian.org, "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>. (Wed, 14 Dec 2011 21:27:09 GMT) Full text and rfc822 format available.

Message #15 received at 652103@bugs.debian.org (full text, mbox):

From: Jose Luis Blanco <joseluisblancoc@gmail.com>
To: martin f krafft <madduck@debian.org>
Cc: 652103@bugs.debian.org
Subject: Re: Bug#652103: ITP: nanoflann -- C++ header-only fork of the FLANN library for KD-trees
Date: Wed, 14 Dec 2011 22:26:46 +0100
Hi Martin,

On Wed, Dec 14, 2011 at 9:40 PM, martin f krafft <madduck@debian.org> wrote:
>> nanoflann is a C++ header-only library for building KD-Trees,
>> mostly optimized for 2D or 3D point clouds.
>
> I won't ask what "clouds" are,

I want to answer that anyway... In the scope of mobile robotics and
computer vision, "point clouds" is a widely used term for "sets of 2D
or 3D points". In fact, one of the most used libraries for related
stuff is named "Point Cloud Library" (PCL) [1], and is maintained by
Willow Garage, a leader company in robotics R&D [2].
All this info is relevant, because one of my initial motivations for
creating nanoflann and for packaging now, was to work in PCL to
replace its usage of flann with this new nanoflann (which, for now, is
~2 times faster for typical operations in mobile robotics).

> but please tell us about how the
> 2D/3D optimisation happens.

Well, in comparison to the original flann, this new lib exploits
templatized code and inlining as much as possible (as I see
libkdtree++ also does). By templatizing the dimensionality of data
points, the generated code typically contains SSE* instructions
instead of loops.

Another important advantage of nanoflann, which I think can't be found
in other libs (note: haven't explored in deep libkdtree++ yet...) is
the usage of data source adaptor classes to avoid allocating memory
for copying of the original data sets: only indices are kept at each
kd-tree node.

>> This implementation is roughly one order of magnitude faster than
>> some other popular KD-tree libraries.
>
> What are other popular KD-tree libraries? And does this apply to
> 2D/3D only?

I personally carried out detailed comparisons vs. flann, with results
shown in [3]. I also compared this new lib to ANN [4] and was about
~50% faster, but didn't make any detailed records or graphs so that
figure is just based on what I recall.

Not personally, I received recently a report of a user which also said
nanoflann was "about one order of magnitude faster than kdtree++" (I
guess that's libkdtree++). I know he works with datasets in the order
of 2^32 data points but I don't know their dimensionality. Perhaps
most of the gain comes from the source data adaptor class, but I'm
just guessing here.


> How does nanoflann compare to libkdtree++? Why would you want to use
> one over the other?

Well, I'm pretty sure it depends on the application, but as said
above, at least for some applications it seems that this new lib makes
sense.


> Note: I am the author of libkdtree++, and I think choice is good.
> However, I simply don't believe some of the claims made in the long
> description, and I question the usefulness of 2D/3D optimisation wrt
> KD-Trees: if you are dealing with only two or three dimensions,
> KD-Trees are usually not what you want. Then again, that was just my
> experience, my KD-Trees usually had dimensions in the low thousands…

Sure, kd-trees are useful for high dimensionality, I've also used them
for that sometimes.

But believe me: there're algorithms in mobile robotics where you have
to look for the nearest points in a set of 2D/3D points (i.e. from
the Microsoft's Kinect sensor) and, in our community, every
implementation which is worth must rely on KD-trees (or similar ideas)
to achieve a reasonable performance.

To get a feeling of what is all this stuff used for, you can see for
example this video [5] (just a quick random search on YouTube, I have
no connection with them!)

Best,
JL

[1] http://pointclouds.org
[2] http://www.willowgarage.com/
[3] http://code.google.com/p/nanoflann/
[4] http://www.cs.umd.edu/~mount/ANN/
[5] http://www.youtube.com/watch?v=pCxbfvEpcXs

-- 
___________________________________________________________

Dr. Jose-Luis Blanco-Claraco
Dpt. Ing. Civil, Mat. y Fabric - Phone: +34 951 952435
E.T.S.I. Industriales - Despacho 2.037
Universidad de Malaga - Campus Universitario de Teatinos
29071 Malaga, Spain
https://sites.google.com/site/jlblancosite/
___________________________________________________________




Information forwarded to debian-bugs-dist@lists.debian.org, wnpp@debian.org, "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>:
Bug#652103; Package wnpp. (Mon, 27 May 2013 14:18:41 GMT) Full text and rfc822 format available.

Acknowledgement sent to Lucas Nussbaum <lucas@debian.org>:
Extra info received and forwarded to list. Copy sent to wnpp@debian.org, "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>. (Mon, 27 May 2013 14:18:41 GMT) Full text and rfc822 format available.

Message #20 received at 652103@bugs.debian.org (full text, mbox):

From: Lucas Nussbaum <lucas@debian.org>
To: 652103@bugs.debian.org
Cc: control@bugs.debian.org
Subject: nanoflann: changing back from ITP to RFP
Date: Mon, 27 May 2013 15:24:12 +0200
retitle 652103 RFP: nanoflann -- C++ header-only fork of the FLANN library for KD-trees
noowner 652103
tag 652103 - pending
thanks

Hi,

This is an automatic email to change the status of nanoflann back from ITP
(Intent to Package) to RFP (Request for Package), because this bug hasn't seen
any activity during the last 12 months.

If you are still interested in adopting nanoflann, please send a mail to
<control@bugs.debian.org> with:

 retitle 652103 ITP: nanoflann -- C++ header-only fork of the FLANN library for KD-trees
 owner 652103 !
 thanks

However, it is not recommended to keep ITP for a long time without acting on
the package, as it might cause other prospective maintainers to refrain from
packaging that software. It is also a good idea to document your progress on
this ITP from time to time, by mailing <652103@bugs.debian.org>.

Thank you for your interest in Debian,
-- 
Lucas, for the QA team <debian-qa@lists.debian.org>



Changed Bug title to 'RFP: nanoflann -- C++ header-only fork of the FLANN library for KD-trees' from 'ITP: nanoflann -- C++ header-only fork of the FLANN library for KD-trees' Request was from Lucas Nussbaum <lucas@debian.org> to control@bugs.debian.org. (Mon, 27 May 2013 14:41:28 GMT) Full text and rfc822 format available.

Removed annotation that Bug was owned by "Jose Luis Blanco (University of Malaga)" <joseluisblancoc@gmail.com>. Request was from Lucas Nussbaum <lucas@debian.org> to control@bugs.debian.org. (Mon, 27 May 2013 14:41:29 GMT) Full text and rfc822 format available.

Send a report that this bug log contains spam.


Debian bug tracking system administrator <owner@bugs.debian.org>. Last modified: Thu Apr 24 02:22:52 2014; Machine Name: beach.debian.org

Debian Bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.