Why not a kd-tree? It’s O(log N ) and it’s in the stand...

The pruning test for a kd-tree is |qi - s| > r. In high-dimensional spaces, such as d=768, the radius r is approximately √2d, which equals 39. Since a single-coordinate gap is typically order 1, the pruning condition almost never fires. Consequently, the kd-tree fails to prune the search space effectively, and the overhead of the tree bookkeeping makes it perform worse than a linear scan.