3 ms·
I thought that k-D trees were good for that problem. With some backtracking in the tree and constructing cutting planes, can get actual nearest neighbor search
by graycat 6y ago
I thought that k-D trees were good for that problem. With some backtracking in the tree and constructing cutting planes, can get actual nearest neighbor search.
- jonas21 6y agokd-trees don't work well for high-dimensional vectors, so when working with embeddings, you typically have to use something else.
- CyberDildonics 6y agoThis hasn't been true for multiple decades at this point. SIFT was originally predicated on best bin first searching through kd-trees to find aproximate nearest neighbors for vectors with over 4000 dimensions. If you prioritize the bins you search by distance, you are are more likely to find closer points sooner. If you are finding a set number of closest points, then you will have a minimum distance to be included in the point set sooner. If that minimum distance is shorter than the distance to a bin, you can skip it.
- thomasahle 6y agoIf you have heuristics fast enough to make kd-trees competitive, it would be interesting to have them added to http://ann-benchmarks.com/ http://ann-benchmarks.com/
- CyberDildonics 6y agoWhat do you mean by "heuristics"? What I described was how flann works. It is not only on those benchmarks but is one of the reasons they exist in the first place, since it instigated a lot of the research into approximate nearest neighbors.
- v4r 6y agoI'm working on a project using kd-tree for high-dimensional embeddings. Could you send me some pointers?
- CyberDildonics 6y agoYou will have to be more specific.