ScaNN: Efficient Vector Similarity Search

Re:ScaNN: Efficient Vector Similarity Search by CyberDildonics on Thursday July 30, 2020 @12:04AM (#23994556)

This 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.

[ Parent | on HN ]

Re:ScaNN: Efficient Vector Similarity Search by thomasahle on Thursday July 30, 2020 @02:17AM (#23995209)

If you have heuristics fast enough to make kd-trees competitive, it would be interesting to have them added to http://ann-benchmarks.com/

[ Parent | on HN ]

Re:ScaNN: Efficient Vector Similarity Search by CyberDildonics on Thursday July 30, 2020 @08:36AM (#23997357)

What 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.

[ Parent | on HN ]

Re:ScaNN: Efficient Vector Similarity Search by v4r on Thursday July 30, 2020 @12:07PM (#23999769)

I'm working on a project using kd-tree for high-dimensional embeddings. Could you send me some pointers?

[ Parent | on HN ]

Re:ScaNN: Efficient Vector Similarity Search by CyberDildonics on Thursday July 30, 2020 @04:19PM (#24002435)

You will have to be more specific.

[ Parent | on HN ]