ingowald / cudaKDTree

203 stars 17 forks source link

Approximate search with eps param #15

Closed bricerebsamen closed 1 year ago

bricerebsamen commented 1 year ago

Reintroducing eps in the search params, which was first introduced in #4 and later removed for some reason. Similar to the same param used in FLANN for approximate nearest neighbor, this affects when to search the far branch: it will check the far branch if far_dist^2 * (1 + eps) is within the search radius (squared). Therefore, for a non-zero value of eps it will search less far branches, resulting in a speed up of the algorithm.

See https://github.com/flann-lib/flann/blob/f9caaf609d8b8cb2b7104a85cf59eb92c275a25d/doc/manual.tex#L875 and https://github.com/flann-lib/flann/blob/f9caaf609d8b8cb2b7104a85cf59eb92c275a25d/src/cpp/flann/algorithms/kdtree_index.h#L615 for the FLANN equivalent

Notes:

ingowald commented 1 year ago

we should make sure that the docs for that variable say that it is optional for the traversal algorithms to use or not use. Ie, we're not promising that every traversal method will respect that value, and certainly not that they all treat it the same way. I.e., different traversal methods may actually return different values if this value is ever set to a non-zero value.