search

flann-lib / flann

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

kdtree_index.h selectDivision() - inconsistency #328

Closed wbrandenburger closed 5 years ago

wbrandenburger commented 7 years ago

Hi,

when you build a kdtree with several trees less than five dimensions, selectdivision() selects randomly a splitdimension instead of take that dimension which shows the highest variance. That leads to an inefficient tree, or rather to an inefficient use of the searchfunction.

Greets from Munich

mariusmuja commented 7 years ago

Hi,

kdtree_index is not meant for low dimensionality points, it's an approximate search algorithm with good performance for high dimensional points. It builds a forest of trees that are searched concurrently, and the slit dimension is intentionally picked at random from the top couple dimensions with highest variance.

For low dimensional points you should use kdtree_single_index, which does exact search.