search

flann-lib / flann

Fast Library for Approximate Nearest Neighbors
http://people.cs.ubc.ca/~mariusm/flann
Other
2.2k stars 646 forks source link

Bug? Radius Search with Autotuned Index #219

Open felixkling opened 9 years ago

felixkling commented 9 years ago

Hi,

I want to perform a fixed radius search with FLANN using the autotuned index (to minimize the search time). My problem involves a large number of point (about a million) at a dimension around 5 - 10 resulting to a number of nearest neighbors in the range 0-10000. I need to find (approximately) all nearest neighbors within a fixed radius. If I use the Autotuned Index, it only gives me the 5-10 nearest neighbors.

I think i found the problem: In "autotunedindex.h" the "bestSearchParams" are used in the function "radiusSearch". When calculating the best search parameters in "estimateSearchParams" also the variable "checks" is evaluated and set to a relatively low number.

Is there an autotuned function available for the radius search that returns all nearest neighbors within the radius?

Felix

andersgb1 commented 9 years ago

Maybe I'm wrong here, but I thought that in any case, if your data has dimension <= 10, then it's always best to use a standard kd-tree ( http://nl.mathworks.com/help/stats/createns.html), which also happens to produce exact results.

On 18 November 2014 00:15, felixkling notifications@github.com wrote:

Hi,

I want to perform a fixed radius search with FLANN using the autotuned index (to minimize the search time). My problem involves a large number of point (about a million) at a dimension around 5 - 10 resulting to a number of nearest neighbors in the range 0-10000. I need to find (approximately) all nearest neighbors within a fixed radius. If I use the Autotuned Index, it only gives me the 5-10 nearest neighbors.

I think i found the problem: In "autotunedindex.h" the "bestSearchParams" are used in the function "radiusSearch". When calculating the best search parameters in "estimateSearchParams" also the variable "checks" is evaluated and set to a relatively low number.

Is there an autotuned function available for the radius search that returns all nearest neighbors within the radius?

Felix

— Reply to this email directly or view it on GitHub https://github.com/mariusmuja/flann/issues/219.

tpet commented 3 years ago

This may be related. I just noticed that one has to use radius squared. Unfortunately, this is not mentioned in the docs. It is nevertheless consistent with FLANN also returning distances squared.